Theory of Computation and Compiler Design 02

11. The equivalent grammar corresponding to the grammar  G : S → aA, A → BB, B → aBb | ϵ is                                                                                                 [Paper III June 2012]

(A) S →  aA,     A →  BB,     B →  aBb

(B) S → a | aA,    A → BB,     B → aBb | ab

(C) S → a | aA,    A → BB | B,     B → aBb

(D) S → a | aA,    A → BB | B,     B → aBb | ab

12. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains                                                                      [Paper III June 2012]

(A) n states                  (B) n + 1 states

(C) n + 2 states            (D) 2n states

13. The following CFG S → aB | bA, A → a | as | bAA, B → b | bs | aBB  

generates strings of terminals that have                        [Paper III June 2012]

(A) odd number of a’s and odd number of b’s

(B) even number of a’s and even number of b’s

(C) equal number of a’s and b’s

(D) not equal number of a’s and b’s

14. The regular expression for the following DFA is      [Paper III June 2012]

(A) ab*(b + aa*b)*           (B) a*b(b + aa*b)*

(C) a*b(b* + aa*b)           (D) a*b(b * + aa*b)*

15. Match the following:                      [Paper III June 2012]

(i) Regular Grammar                           (a) Pushdown automaton

(ii) Context free Grammar                   (b) Linear bounded automaton

(iii) Unrestricted Grammar                  (c) Deterministic finite automaton

(iv) Context Sensitive Grammar          (d) Turing machine

(i)         (ii)        (iii)       (iv)

(A)       (c)        (a)        (b)       (d)

(B)       (c)        (a)        (d)       (b)

(C)       (c)        (b)        (a)       (d)

(D)       (c)        (b)        (d)       (a)

16. Consider the following statements:           [Paper II June 2012]
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true?

(A) I only                    (B) I and II

(C) I and III                (D) II and III

SOLUTIONS

11. D

Strings that are legal according to the given grammar is a, aab, aabab etc

Out of the options the grammar that can produce all these strings is D

Option B seems to be correct in first look, but fails to produce  aab.

12.

13.

14. D

15. B

Grammar Type	Language	machine
Type 0	Recurssively Enumerable/ Un restricted/ Phase structured/ Semithus	Turing Machine
Type 1	Context Sensitive	Linear Bounded Automata
Type 2	Context Free	Pushdown Automata
Type 3	Regular	Finite Automata

16. B

Recursively enumerable languages are closed under the following operations:

• Kleene star L*
• concatenation of L and P
• union of L and P
• intersection L and P.

Recursive languages are closed under the following operations:

• Kleene star L*
• Concatenation L and P
• Union L and P
• Intersection L and P
• Complement of L
• Set difference L - P

So only Statements I and II are true.

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.