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 1^a01^b01^c. For instance, you could write "repeat rule X a times" as part of it.

JFLAP

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

Problem 1.3 (3 Points)

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

Hint: Believe it or not, L₂ 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 L₂ 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

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

Input	Result
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

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

Input	Result
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

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 w^R, 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.

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

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

Input	Result
00#111	Reject
01010#11001100	Reject
101100#10110	Reject
01010#10100101	Reject
01011100#01110100	Reject

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)

Input	Result
01011011	Reject
11001100	Accept
0111001100	Accept
0101110010	Accept
001111	Reject
000000110	Reject
10001	Reject
11001000	Reject
0101101001	Accept
00100111	Accept