### SET 5

Question 1

**Which of the following problems is undecidable?**

A : Membership problem for CFGs

B : Ambiguity problem for CFGs.

C : Finiteness problem for FSAs

D : Equivalence problem for FSAs

Answer Discuss it!

.

Correct answer is :B

Solution :

Ambiguity problem for CFGs are not decidable.

Question 2

**Which of the following is TRUE?**

A : Every subset of a regular set is regular

B : Every finite subset of a non-regular set is regular

C : The union of two non-regular sets is not regular.

D : Infinite union of finite sets is regular

Answer Discuss it!

.

Correct answer is :B

Question 3

**A minimum state deterministic finite automaton accepting the language L={W | W ε {0,1} *, number of 0s and 1s in are divisible by 3 and 5, respectively} has**

A : 15 states

B : 11 states

C : 10 states

D : 9 states

Answer Discuss it!

.

Correct answer is :A

Question 4

**The language L= {0**^{i}21^{i} | i≥0 } over the alphabet {0,1, 2} is:

A : not recursive

B : is recursive and is a deterministic CFL

C : is a regular language

D : is not a deterministic CFL but a CFL

Answer Discuss it!

.

Correct answer is :B

Question 5

**Which of the following languages is regular? **

A : {ww^{R} | w ∈ {0,1}^{+}}

B : {ww^{R}x | x,w ∈ {0,1}^{+}}

C : {wxw^{R} | x,w ∈ {0,1}^{+}}

D : {xww^{R} | x,w ∈ {0,1}^{+}}

Answer Discuss it!

.

Correct answer is :C

Question 6

**Consider the grammar with non-terminals N = {S,C,S1 },terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:**

S --> iCtSS1|a

S1 --> eS|?

C --> b

The grammar is NOT LL(1) because:

A : it is left recursive

B : it is right recursive

C : it is amiguous

D : it is not context free

Answer Discuss it!

.

Correct answer is :C

Question 7

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

A : b* ab* ab* ab*

B : (a+b)*

C : b*a(a+b)*

D : b*ab*ab*

Answer Discuss it!

.

Correct answer is :C

Question 8

**Consider the following Finite State Automaton:**

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

A : 1

B : 2

C : 3

D : 4

Answer Discuss it!

.

Correct answer is :B

Question 9

**Which of the following is true for the language { a**^{p} | p is prime }

A : It is not accepted by a Turing Machine

B : It is regular but not context-free

C : It is context-free but not regular

D : It is neither regular nor context-free, but accepted by a Turing machine

Answer Discuss it!

.

Correct answer is :D

Question 10

**Which of the following are decidable? **

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

A : I and II

B : I and IV

C : II and III

D : II and IV

Answer Discuss it!

.

Correct answer is :B

Question 11

**If L and L' are recursively enumerable, then L is**

A : regular

B : context-free

C : context-sensitive

D : recursive

Answer Discuss it!

.

Correct answer is :D

Solution :

If L is recursively enumerable, then L' is recursively enumerable if and only if L is also recursive.

Question 12

**Which of the following statements is false?**

A : Every NFA can be converted to an equivalent DFA

B : Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machin

C : Every regular language is also a context-free language

D : Every subset of a recursively enumerable set is recursive

Answer Discuss it!

.

Correct answer is :D

Question 13

**Given below are two finite state automata (? indicates the start state and F indicates a final state)Which of the following represents the product automaton Z×Y?**

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :A

Question 14

**Match the following:**

A : E - P, F - R, G - Q, H - S

B : E - R, F - P, G - S, H - Q

C : E - R, F - P, G - Q, H - S

D : E - P, F - R, G - S, H - Q

Answer Discuss it!

.

Correct answer is :C

Question 15

**Match the following NFAs with the regular expressions they correspond to**

1. ε + 0(01*1 + 00) * 01*

2. ε + 0(10 *1 + 00) * 0

3. ε + 0(10 *1 + 10) *1

4. ε + 0(10 *1 + 10) *10 *

A : P - 2, Q - 1, R - 3, S - 4

B : P - 1, Q - 3, R - 2, S - 4

C : P - 1, Q - 2, R - 3, S - 4

D : P - 3, Q - 2, R - 1, S - 4

Answer Discuss it!

.

Correct answer is :C

Question 16

**Which of the following are regular sets?**

I. { a^{n} b^{2m} |n >=0,m >= 0}

II. { a^{n} b^{m} |n = 2m }

III. { a^{n} b^{m} |n ≠ m}

IV. {xcy x, y ε{a,b} *}

A : I and IV only

B : I and III only

C : I only

D : IV only

Answer Discuss it!

.

Correct answer is :A

Solution :

We can write DFA for both I and IV.

Question 1

.

Correct answer is :B

Solution :

Ambiguity problem for CFGs are not decidable.

Question 2

.

Correct answer is :B

Question 3

.

Correct answer is :A

Question 4

^{i}21

^{i}| i≥0 } over the alphabet {0,1, 2} is:

.

Correct answer is :B

Question 5

.

Correct answer is :C

Question 6

S --> iCtSS1|a

S1 --> eS|?

C --> b

The grammar is NOT LL(1) because:

.

Correct answer is :C

Question 7

.

Correct answer is :C

Question 8

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

.

Correct answer is :B

Question 9

^{p}| p is prime }

.

Correct answer is :D

Question 10

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

.

Correct answer is :B

Question 11

.

Correct answer is :D

Solution :

If L is recursively enumerable, then L' is recursively enumerable if and only if L is also recursive.

Question 12

.

Correct answer is :D

Question 13

.

Correct answer is :A

Question 14

.

Correct answer is :C

Question 15

1. ε + 0(01*1 + 00) * 01*

2. ε + 0(10 *1 + 00) * 0

3. ε + 0(10 *1 + 10) *1

4. ε + 0(10 *1 + 10) *10 *

.

Correct answer is :C

Question 16

I. { a

^{n}b

^{2m}|n >=0,m >= 0}

II. { a

^{n}b

^{m}|n = 2m }

III. { a

^{n}b

^{m}|n ≠ m}

IV. {xcy x, y ε{a,b} *}

.

Correct answer is :A

Solution :

We can write DFA for both I and IV.