Lab 06

Exercise 01

Produce context-free grammars for the following languages. Replacement rules are all you need—it’s not necessary to write out complete 4-tuples. $\Sigma =\{0,1\}$

1. Problem A

$$A=\{w\mid thelengthofwiseven\}$$ $$\begin{array}{rl}A\to & ϵ|\Sigma B\\ & \\ B\to & \Sigma |A\end{array}$$

2. Problem B

$$B=\{w\mid thelengthofwisodd,andthemiddlesymbolis0\}$$ $$\begin{array}{r}A\to 0A1|1A0|ϵ\end{array}$$

3. Problem C

$$C=\{w\mid whasthesamenumberof0sand1sinanyorder$$ $$\begin{array}{rl}S& \to 0S1|1S0|SS|ϵ\end{array}$$

---

Exercise 02

Context-free languages are close under union. That is, if $A$ and $B$ are context-free, then the language $A\cup B$ is also context-free.

Produce CFGs for the following languages, using the definitions from exercise 01:

1. Problem A

$$A\cup B$$ $$S\to \Sigma S\Sigma |ϵ$$

2. Problem B

$$B\cup C$$

---

Exercise 03

Prove that the following languages are context-free by providing context-free grammars that generate them.

1. Problem A

$$A=\{a^m{b}^n{c}^n\mid m,n\ge 0\}$$

Defining this with start symbol $S$, nonterminals $A$ and $B$ to generate any number $a$‘s or the balanced part $b^n{c}^n$

We get:

$$\begin{array}{rl}S& \to AB\\ A& \to aA\mid ϵ\\ B& \to bBc\mid ϵ\end{array}$$

2. Problem B

$$B=\{a^n{b}^n{c}^m\mid m,n\ge 0\}$$

Defining this with start symbol $S$, nonterminals $A$ and $C$ to generate the balanced part $a^n{b}^n$ or any number of $c$‘s

$$\begin{array}{rl}S& \to AC\\ A& \to aAb\mid ϵ\\ C& \to cC\mid ϵ\end{array}$$

---

Exercise 04

Given the two languages, $A$ and $B$ from exercise 03, write the language $A\cap B$ using set builder notation.

To complete problem we let a string be $a^x{b}^y{c}^z$, for the previously defined $A$ and $B$

For String to be in $A$:

• must be integers $m$ and $n$ so that $x=m$, $y=n$, and $z=n$

and thus the condition for $A$ is $z=y$

For String to be in $B$:

• must be integers $n^{\prime }$ and $m^{\prime }$ so that $x=n^{\prime }$, $y=n^{\prime }$, and $z=m^{\prime }$

and thus the condition for $B$ is $x=y$

Therefore:

$$A\cap B=\{a^n{b}^n{c}^n\mid n\ge 0\}$$

---

Exercise 05

Consider the language $\{0^n{1}^n{0}^n\mid n\ge 0\}$, which is not context-free

1. How is this language similar to the language $A\cap B$ from exercises 03 and 04?
2. What does this suggest about certain closure properties of context-free languages