**Ursinus CS 373: Theory of Computation, Fall 2023**

## 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

- (2 points)
Which strings can be generated with 4 or fewer substitutions?

- (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**. For instance, you could write "repeat rule X a times" as part of it.^{a}01^{b}01^{c}

#### 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

### \[ 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 **L _{2}** with a DFA.

**Hint: ** Believe it or not, **L _{2}** 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.

_{2}### 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)

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

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

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

### \[ 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 **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 |