Lab 05

Problems and topics listed here are for open discussion and practice. Feel free to work with a partner or ask the instructor questions. Towards the end of the lab period we may review some but not necessarily all answers. You are welcome to discuss solutions and strategies to these problems openly with classmates and the instructor outside of lab/class, on Piazza, and office hours.

You do not need to submit any solutions to these problems. This work will not be graded.

1. Consider the PDA from class that recognizes $L=\{a^nb^n, n \geq 1\}$. Add states and/or transitions so that the PDA recongnizes $L=\{a^nb^n, n \geq 0\}$. Modify the PDA so that it still has one final accept state and each transition is either a push or pop transition. What new rules will you add to the grammar discussed in class so that grammar can now generate $\varepsilon$?
2. Let $L_1=\{ x\#y, |x| =|y| \}$, where $x,y \in \{a,b\}^*$. Design a grammar for $L_1$.
3. Let $L_2=\{ x\#y, |x| \not = |y| \}$, where $x,y \in \{a,b\}^*$. Design a grammar for $L_2$.
4. Let $L_3=\{ x\#y, x \not = y \}$, where $x,y \in \{a,b\}^*$. Describe a PDA that recognnizes $L_3$.
5. For a regular language $L$, the pumping length $p$ is the number of states in the DFA that recognizes $L$. For context free grammars, the pumping lemma for CFLs states that for strings longer than some pumping length $p$, we must repeat a variable in the grammar $G$ that generates $L$. Suppose the grammar has $|V|$ variables. Sketch out a parse tree and assign an upper bound $b$ to the number of symbols on the right hand side of any rule in the grammar. What is the maximum number of symbols we can produce without repeating a variable? What is the pumping length for a CFG?