Quiz about Theory of Computation and Compiler Design

Question 1

Let L={w \in (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Accepted Answer

0*(10*10*)*

Answer

(0*10*1)*

Answer

0*(10*1*)*0*

Answer

0*1(10*1)*10*

Question 2

Consider the languages 
L1={0^{i}1^{j}|i != j}, 
L2={0^{i}1^{j}|i = j}, 
L3 = {0^{i}1^{j}|i = 2j+1}, 
L4 = {0^{i}1^{j}|i != 2j}. 
Which one of the following statements is true?

Accepted Answer

All are context free

Answer

Only L2 is context free

Answer

Only L2 and L3 are context free

Answer

Only L1 and L2 are context free

Question 3

Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Accepted Answer

n+1

Answer

n-1

Answer

n

Answer

2n-1

Question 4

Let L = L1 \cap L2, where L1 and L2 are languages as defined below: 
L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is

Accepted Answer

Context free but not regular

Answer

Not recursive

Answer

Regular

Answer

Recursively enumerable but not context free.

Question 5

Consider the language L1,L2,L3 as given below. 
L1={0^{p}1^{q} | p,q \in N}
L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}
Which of the following statements is NOT TRUE?

Accepted Answer

All the three languages are context free

Answer

Push Down Automata (PDA) can be used to recognize L1 and L2

Answer

L1 is a regular language

Answer

Turing machine can be used to recognize all the three languages

Question 6

Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?

Accepted Answer

n+1

Answer

k+1

Answer

2^(n+1)

Answer

2^(k+1)

Question 7

Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then is L’ (complement of L) also context-free?
3) If L is a regular language, then is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?

Accepted Answer

3, 4

Answer

1, 2, 3, 4

Answer

1, 2

Answer

2, 3, 4

Question 8

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are

Accepted Answer

D

Answer

A

Answer

B

Answer

C

Question 9

Consider the following Finite State Automaton
The language accepted by this automaton is given by the regular expression

Accepted Answer

b*a(a+b)*

Answer

b*ab*ab*ab

Answer

(a+b)*

Answer

b*ab*ab

Question 10

The minimum state automaton equivalent to the above FSA has the following number of states

Accepted Answer

2

Answer

1

Answer

3

Answer

4

Practice Test On: Theory of Computation and Compiler Design

Practice Test On:
Theory of Computation and Compiler Design