Theory of Computation and Compiler Design 01

1. The grammar ‘G1’ S → OSO| ISI | 0|1|ϵ and the grammar ‘G2’ is S → as |asb| X, X → Xa | a. Which is the correct statement ?                                                          [Paper III December 2012]

(A) G1 is ambiguous, G2 is unambiguous

(B) G1 is unambiguous, G2 is ambiguous

(C) Both G1 and G2 are ambiguous

(D) Both G1 and G2 are unambiguous

2. Which of the following regular expression identities are true?    [Paper III December 2012]

(A) (r + s)* = r* s*

(B) (r + s)* = r* + s*

(C) (r + s)* = (r*s*)*

(D) r* s* = r* + s*

3. The minimum number of states of the non-deterministic finite automation which accepts the language                                                                                                   [Paper III December 2012]

{a b a bⁿ | n ≥ 0} U {a b aⁿ|n ≥ 0} is

(A) 3                (B) 4

(C) 5                (D) 6

4. Which of the following definitions generates the same Language as L,

where L = {WWR | W ϵ {a, b}*}                                    [Paper III December 2012]

(A) S → asb|bsa|ϵ

(B) S → asa|bsb|ϵ

(C) S → asb|bsa|asa|bsb|ϵ

(D) S → asb|bsa|asa|bsb

5. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length                                   [Paper III December 2012]

(A) no greater than 2ⁱ⁺¹

(B) no greater than 2ⁱ

(C) no greater than 2^i–1

(D) no greater than i

6. Given the following statements:                                    [Paper III December 2012]

(i) Recursive enumerable sets are closed under complementation.

(ii) Recursive sets are closed under complementation.

Which is/are the correct statements ?

(A) only (i)

(B) only (ii)

(C) both (i) and (ii)

(D) neither (i) nor (ii)

7. Which one of the following statement is false?              [Paper II December 2011]

(A) Context-free languages are closed under union.

(B) Context-free languages are closed under concatenation

(C) Context-free languages are closed under intersection.

(D) Context-free languages are closed under Kleene closure.

8. Given the following statements:                                 [Paper III June 2012]

(i) The power of deterministic finite state machine and nondeterministic finite state machine are same.

(ii) The power of deterministic pushdown automaton and nondeterministic pushdown automaton are same.

Which of the above is the correct statement(s)?

(A) Both (i) and (ii)

(B) Only (i)

(C) Only (ii)

(D) Neither (i) nor (ii)

9. Which is not the correct statement(s)?                  [Paper III June 2012]

(i) Every context sensitive language is recursive.

(ii) There is a recursive language that is not context sensitive.

(A) (i) is true, (ii) is false.

(B) (i) is true and (ii) is true.

(C) (i) is false, (ii) is false.

(D) (i) is false and (ii) is true.

10. Which one of the following is not a Greibach Normal form grammar?  

                                                                           [Paper III June 2012]

(i) S →a | bA | aA | bB

A →a

B →b

(ii) S →a | aA | AB

A →a

B →b

(iii) S →a | A | aA

            A →a

(A) (i) and (ii)

(B) (i) and (iii)

(C) (ii) and (iii)

(D) (i), (ii) and (iii)

SOLUTIONS

1. B

A context-free grammar is said to be an ambiguous grammar if there exists a string which can be generated by the grammar in more than one way (i.e. the string admits more than one parse tree or, equivalently, more than one leftmost derivation).

Any grammar can be proved ambiguous if we are able to find at least one string with more than one left-most derivation accepted by the grammar. In the given question we cannot find any such strings for G1. Consider G2, take the case of aaa, two possible derivations are:

(1)   S   → aS                                                     (2)   S   → aS

            → aX     // Using S→ X                                        →aaS    // Using S → aS

            → aXa   // Using X→ Xa                                      →aaX    // Using S → X

            → aaa   // Using X → a                                        →aaa     // Using S → a

So G1 is unambiguous and G2 is ambiguous

2. C

 (r + s)* should be understood as any number of repetitions of r OR s. It can be thought of as a bag containing r and s, and we taking out any of these one by one.

r* s* says 0 or more r followed by 0 or more s, there is no scope or any r after any s. So they are not equivalent.

r* + s* says either r* OR s*, so this is also not equivalent.

(r*s*)* says a bag containing string with 0 or more r followed by 0 or more s. we can take out 0 or more strings one by one. Using this we can construct any string defined by (r + s)*. So this is the answer.

3. B   (But UGC says C!!)

The regular expressions corresponding to the given language is { abab* U aba*} = aba*b*

The NFA can be drawn as 

So we need only 4 states to represent this language.

4. B

5. C

6. B

7. C
Context-free languages are not closed under: intersection and complement.
Context-free languages are closed under: union, concatenation, star, string reversal, homomorphism and intersection with a regular language

8.

9.

10.