Lab 05

Exercise 01

The pumping lemma for regular languages (Sipser, Theorem 1.70) states: “If $A$ is a regular language, then there is a number $p$ where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces $s=xyzs=xyz$, satisfying the following conditions:

$$\begin{array}{rl}& 1.foreachi\ge 0,x{y}^{i}z\in A,\\ & 2.\mid y\mid >0[thatis,y\ne ϵ],and\\ & 3.\mid xy\mid \le p^{\prime \prime }\end{array}$$

Write a proof by contradiction which uses the pumping lemma to show that the language $L=\{0^m{1}^n{0}^m|n,m\in N\}$

is not regular.

1. Supposing towards $\Rightarrow \Leftarrow$ this language $L$ is regular and consider the string $s=0^{m-1}01^n{0}^m$
2. Matching all the conditions
3. Now pumping this we can get strings that are unbalanced and not in the language

$\cup$ set union $\cap$ set intersection $\in$ set membership $\notin$ not a member $\ge$ greater than or equal to $\le$ less than or equal to

---

Exercise 02

Consider the following context-free grammar, $G$:

$$\begin{array}{rl}& A\to DAD\mid B\\ & B\to aCb\mid bCa\\ & C\to DCD\mid D\mid ϵ\\ & D\to a\mid b\end{array}$$

1. What are the variables of $G$?
   • $G=\{A,B,C,D\}$
2. What are the terminals of $G$?
   • $\{a,b\}$
3. What is the start variable of $G$?
   • $A$
4. Give three strings in $\mathcal{L}(G)$
   1. $A\to B\to aCb\to ab$, therefore $ab\in \mathcal{L}(G)$
   2. $A\to B\to aCb\to aDCDb\to aaCab\to aaϵab\to aaab$, therefore $aaab\in \mathcal{L}(G)$
   3. $A\to DAD\to aAa\to aBa\to abCa\to abaa$, therefore $abaa\in \mathcal{L}(G)$
5. Give three strings not in $\mathcal{L}(G)$.
   1. $aa:$ smallest valid string require at least one occurrence $a$ and $b$ together, so $aa\notin \mathcal{L}(G)$
   2. $bb:$ for same reason as above, requires at least one $a$, therefore $bb\notin \mathcal{L}(G)$
   3. $abb:$ if $A\to B$, the $B$ must produce a pattern of $aCb$ or $bCa$ for symmetry. $abb$ does not fit this pattern, therefore $abb\notin \mathcal{L}(G)$

---

Exercise 03

Consider the grammar given in Exercise 02, and answer true or false to the following:

1. $C\to aba$
   • $False$
2. $C{\to }^{\ast }aba$
   • $True$
3. $C\to C$
   • $False$
4. $C{\to }^{\ast }C$
   • $True$
5. $DDD{\to }^{\ast }aba$
   • $True$
6. $D{\to }^{\ast }aba$
   • $False$
7. $C{\to }^{\ast }DD$
   • $True$
8. $B{\to }^{\ast }ϵ$
   • $False$

---

Exercise 04

Consider this context-free grammar, $H$

$$\begin{array}{rl}& E\to E+T\mid T\\ & T\to T\times F\mid F\\ & F\to (E)\mid a\end{array}$$

Give a parse tree and leftmost derivations for the following strings:

1. $a+a$
2. $((a))$

---

Exercise 05

Explain, in plain English, in a sentence or two, the meaning of

$$\mathcal{L}(G)=\{w\in {\Sigma }^{\ast }\mid S{\to }^{\ast }w\}$$

with respect to context-free languages, i.e., where $G$ is some context-free grammar, and $S$ is the start variable.

This Grammar constructs languages that start with the symbol $S$ and have symbols in the language $$