Class Work 9 for CMP 416/685: Computability Theory, CUNY, Fall 2016

Grading Notes:

Submit one answer per group.
Make sure that the answer is legible.
Include the full names of all group members on your submitted work (so all get credit).

Consider the context-free grammar (variation of the example from the textbook):

S  -> NP VP
NP -> CN | CN PP
VP -> CV | CV PP
PP -> P CN
CN -> A N
CV -> V | V NP
A  -> a | the
N  -> armadillo | bat | cat | dog
V  -> talks | likes | jumps
P  -> with | for

Give two strings that are generated by the grammar.
Give two strings that are not generated by the grammar.
What is the shortest string generated by the grammar?
What is the longest?

Class Work 9: Context Free Grammars

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Class Work 9: Context Free Grammars

Computer Science 416/685: Computability Theory Lehman College, City University of New York Fall 2016

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016