COM1350 Automata Theory Exam 3 Spring 1998 Professor Fell
Name:

Problem 1: (20 points)
For each of the grammars below, give a parse tree for each string of length <= 4 that can be generated by the grammar.

a.S --> aAS | a
 A --> SbA | SS | ba
b.S --> aSb | X
 X --> aXa | a

Problem 2: (20 points)
Give a context free grammar that generates

{ axbyaz | x, z >= 0, and y = x + z }

Hint: This is the same as: { axbxbzaz | x, z >= 0 }

Problem 3: (20 points)
Give a pushdown automata that recognizes

{ axbyaz | x, z >= 0, and y = x + z }

Problem 4: (20 points)
Convert the deterministic finite state automaton below to a context free grammar.
Use the algorithm described in class and in the book

Problem 5: (20 points)
Use the pumping lemma to show that the following language is not regular: { akbmcn | k < m < n } The alphabet = {a, b, c}

Last Updated: May 22, 1999 4:12 pm by

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1350/test3.html