Homework 5: Context Free Grammars And Pushdown Automata (25 Points)

Chris Tralie

Overview / Logistics

The purpose of this problem set is to get you experience designing and reasoning about context free grammars, as well as designing pushdown automata, which will serve as a warmup to our ultimate destination in this course: Turing machines.

Part 1: Context-Free Grammars

Problem 1.1 (4 Points)

Consider the grammar with variables V = {S, R}, terminals Σ = {0, 1} and the following rules (where S is the start variable)

  • S → RR
  • R → RRR
  • R → 0
  • R → 1R
  • R → R1

  1. (2 points)

    Which strings can be generated with 4 or fewer substitutions?

  2. (2 Points)

    For arbitrary a, b, c ≥ 0, describe a derivation (sequence of rules repeating in terms of a, b, and c) that lead to the terminal string 1a01b01c. For instance, you could write "repeat rule X a times" as part of it.


To help you out, you can take advantage of JFLAP's built-in CYK parser which finds a valid derivation if it exists. Open up the Grammar program in JFLAP, then write in the rules for the grammar. Then, go to the menu Input → CYK Parse. You can put in a string here. If the string is in the language, JFLAP will find a derivation using the CYK algorithm, which you can display either as a derivation table

or as a parse tree, which you can go through step by step

If the string you input is not in the language generated by the CFG, then it will say it was rejected.

Problem 1.2 (3 Points)

Devise a context free grammar that generates the language

\[ L_2 = \{a^ib^jc^k | i, j, k \geq 0 \text{ and if } i = 1, \text{ then } j = k \} \]

Problem 1.3 (3 Points)

Prove that it's impossible to recognize the above language L2 with a DFA.

Hint: Believe it or not, L2 actually satisfies the regular pumping lemma! But this doesn't imply it's regular. Recall that being regular implies the pumping lemma, but the converse is not necessarily true; that is, a language that satisfies the pumping lemma is not necessarily regular. In fact, this is a counter-example to the converse of the pumping lemma. Instead, assume L2 is regular and use other properties of regular languages to transform it into something else that's nonregular, which would be a contradiction.

Problem 1.4 (3 Points)

We know that the union of two CFGs is a CFG, and that CFG generated languages are a superset of regular languages. However, this doesn't preclude the union of two CFGs from being regular. To prove this, show two languages which are each nonregular but which can be each generated with CFGs, and whose union is regular.

Hint: If you're stuck, try consider languages of strings with a bunch of 0s followed by a bunch of 1s

Part 2: Pushdown Automata

What's neat about all of the languages in these problems is that they aren't regular (you could prove this with the pumping lemma), but they're still simple enough that just having a rudimentary stack for memory is enough to recognize them.

In all of the problems below, you should design and submit a JFLAP file. Be sure to only push or pop one character at a time.

Problem 2.1 (3 Points)

Design a pushdown automaton that recognizes the following language

\[ L = \{ a^{2n}b^{5n} | n \geq 0 \} \]

Below are some tests you can try in JFLAP (Click here to download them)

aabbbbb Accept
aabbbbbb Reject
aaabbb Reject
aaaaaabbbbbbbbbbbbbbb Accept
aaaaaaaabbbbbbbbbbbbbbbbbbbb Accept
aabb Reject
aaaaaaaabbbbbbbbbbbbbbbbbbbbbb Reject
aabbbbbbbbbb Reject
aaabbbbb Reject

Problem 2.2 (3 Points)

Design a pushdown automaton that recognizes the following language

\[ L = \{ a^nb^mc^md^n | m, n \geq 0 \} \]

Below are some tests you can try in JFLAP (Click here to download them)

aabbbbb Reject
aaaddd Accept
aaabcddd Accept
abbbbccccd Accept
abbbbccccdd Reject
bbbbcccc Accept
bbbbccccc Reject
aabbbbccccdd Accept
dcba Reject

Problem 2.3 (3 Points)

Design a pushdown automaton that recognizes the following language

\[ L = \{w\#x | w^R \text{ is a substring of } x \text{ for } w, x \in \{0,1\}^* \}\]

Below are some tests you can try in JFLAP that should all accept (Click here to download them). I'm showing w in red and wR, the reverse of w, in blue. The entire substring after the red portion is x. I'm separating these tests out because with nondeterminism, it's possible that JFLAP will warn you that a ton of configurations are being generated, so it's nice to do these ones separately.

10110#1111011011 Accept
00101#01010100 Accept
1110100#01000101110 Accept
01010#10100101001 Accept
01011100#0000001110100 Accept
#0101Accept (Empty w)

Below are some inputs that should be rejected (Click here to download them). These tests will run faster


Problem 2.4 (3 Points)

The following context free grammar generates the language of binary strings with the same number of 1s as 0s

  • S → λ
  • S → 0S1S
  • S → 1S0S

Devise a pushdown automaton that recognizes the same language. Below are some tests you can apply in JFLAP (Click here to download them)