CIS-303: Homework 6: (80 points)
1. Give a context-free grammar for the following language L:
L = fakbjcjdkg
2. Design a pushdown automaton for the language L in the above problem.
3. Design a context-free grammar for the following language L:
L=fanbbbc3nr where n>0g
(This was a problem on last year’s second midterm exam.)
4. Design a context-free grammar for the set L of balanced strings of delimeters of two
types () and . For example, ([()]()) is in L but [(]) is not.
5. Design a nondeterministic pushdown automaton that recognizes the following lan-
L=faibjck where i
6. Give a context-free grammar for the following language L:
L = fw2f1,2,3,4g j w does not contain the substring 222g
7. Consider the following grammar:
Show that the above grammar is ambiguous by giving two dierent derivation trees
for the string aabbbb
8. Consider the following grammar:
Show that the above grammar is ambiguous by nding a string with two dierent
derivation trees. You must give the string and draw the derivation trees.
Such a cheap price for your free time and healthy sleep
All online transactions are done using all major Credit Cards or Electronic Check through PayPal. These are safe, secure, and efficient online payment methods.