COT 3210 Exam 2. Answer All Questions. Each Question Worth 10 Points

Name: ______________________________

COT 3210 Exam 2. Answer all questions. Each question worth 10 points.

1. Use the pumping lemma to prove that 0n1m, n ³ m, is not regular.

Let n be plc

z=0n12n, z=uvw. Let z’=uw. But z’ has fewer 0’s than 1’s.

2. Prove that L = 0nww0n , n > 0, not regular, where w is a string.

Let n be plc. z=0n110n. z=uvw. z’=uvvw= 0n+q110n, q >=1, but z’ is not in L.

3. Give a context-free grammar to generate the language 0n1m, n ³ m.

S -> ASB | e

A -> 0A|0

B -> 1 | e

4. Give a context-free grammar to generate the language (0+1)0*(11)*.

S-> ABC

A -> 0 | 1

B -> 0B | e

C -> 11C | e

For the next two questions, consider the CFG (S is the start symbol):

S -> SA | a

A -> Aa | aB

B -> bB | SB | b

5. Show how to derive the string aabab using this CFG using a left-most derivation.

S -> SA -> aA -> aaB -> aabB -> aabSB -> aabaB -> aabab

6. Show a parse tree for the string aabb

7. Describe (at a very high level) a PDA to accept sets of “balanced” “{“ and “ }” symbols from a “C” program. That is, the alphabet consists of the two symbols: “{“ and “}” Strings are sequences of these symbols such that no prefix of the string has more “}” than “{“. For example, the following is legal: {{}{}}, but the following string is not: {}}{.

Push {‘s. Pop { when you read a }. Accept by empty stack.

8. Suppose we have a finite automata with TWO stacks (instead of just one stack as with PDA). Describe at a very high level how we can accept 0n1n2n using this type of machine.

Push 0’s on stack 1 and stack 2 at same time. Read 1’s and pop 0’s from stack 1. Read 2’s and pop 0’s from stack 2. Accept only if both stacks empty.