90s Masters Exam - Automata

Theory of Automata Master's Examination Fall 1995, 1 hour

Problem 1) Find the minimal DFA for the regular expression

(a*b+ b*)(ab)*

Problem 2) Convert the context free grammar G

into a context free grammar G which generates L(G) - {A). The grammar G should be without unit productions, without A-productions, and should not have useless productions or useless variables. Problem 3) Prove if L is a non-regular language and F a finite language then L UF is a non-regular language. Problem 4) Show that the language

L = {an I n is not a prime number] is not regular. Problem 5) For the grammar G

S-iaSbIaIb construct a deterministic pushdown automata, which recognizes with empty stack the language defined by G.

Automata Theory Master's Examination Spring 1995, 1 hour

1. Construct a nondeterministic pushdown automata, which accepts the language defined by the grammar

Can youconstruct a deterministic pushdown automata for the same .. language? . .

.

.

2. Show that the following. grammar is ambiguous . . .

but that the corresponding language is not ambiguous. 3. Convert the following regular grammar to a left-linear grammar, which generates the same language

4. Proof that the set of regular languages is closed under intersections. 5. Proof that the language

is not regular.

Instructions: Do 5 of the following 6 problems. 1. For each natural number n

> 0, let L, = {a, b)'a{a,

(a) Construct an NFA with n

()"-I.

+ 1states which accepts L,.

(b) Construct a DFA with 2" states which accepts L,. If you construct your DFA by an algorithm or tabular method from an NFA, carry out the construction for n = 3. If you construct your DFA directly, describe the construction for each n > 0. 2. (a) Prove that if a language L E {a, b)' is regular, so is {a, b)' - L. (b) Prove that if languages L1, L2 C {a,b)' are regular, then L1 U L2 is also regular.

(c) Prove that there are languages L1, L2E {a, b)' which a n not regular but where L1 U L2 is regular. 3. Use the pumping lemma to show that the language L = {aibi@d : i = 0 or j = k = I ) is not regular.

4. (a) Write a T in each box below if the corresponding type of automaton can recognize all languages of the corresponding type. "D" and "N" stand for "deterministic" and "nondeterministic." "SB" stands for "space-bounded." "TM" stands for "Turing machine."

DFA NFA

DPDA NPDA

SBTM DTM

NTM

regular languages context-free languages context-sensitivelanguages unrestricted languages (b) Of the four classes of languages above (regular, context-fiee, context-sensitive, and unrestricted), identify the first of these languages classes to which each of the following languages belongs. Belo*, na(z) denotes the number of a's in string z.

i. {an : n > 0). ii. {anan : n > 0). iii. {anbnan : n > 0). iv. {Z E {a, b)' :nl(z) < nb(z)). V. {z E {a, b)' : no(z) = nb(z), and for all prefixes y of z, na(y) 2 ~ ( y ) ) .

-

5. Construct a non-deterministic pushdop automaton which accepts the language defined by the grammar s -r 050 I 151 ( c. The pushdown automaton should have only one state and should accept by empty stack. (Recall that an automaton accepts a string by empty stack if, after reading the string, it halts - in any state - with an empty 8 t h . )

6. (a) Prove that the intersection of a regular language and a context-freelanguage is contextfie. (b) Is the language of problem 3 context fiee?

AUTOMATA THEORY

MASTERS EXAM

ONE HOUR

Saturday April 3,1993

1) Produce a dfa for the language L(a(b+A)(bbbb)*).

2) Produce a grammar for the language {ab2"c3": n 2 0). 3) Given the grammar G with productions S + aAB IA, A 4 bas 1a, B construct an nfa which accepts the language L(G).

+

BA IA,

4) Construct an nfa M so that L(M) = L(r), where r is the regular expression

r = (a(aaa)* (A + b)b)*

+ ((a+b)(a+b))*

5) Find a left linear grammar for the language recognized by the automaton in problem 1. 6) The following grammar G is in Greibach normal form. Produce a nondeterministic pushdown automaton which accepts the language YG):

S-aSB I aB, B 4 b .