FORMAL Language 2019 Final

Q1.

(10 points) Find an s-grammar for the language

$L=\{a^n{b}^{n+1}:n\ge 3\}$.

Solution

$$\begin{array}{lll}S& \to & a{S}_{1}B\\ S_1& \to & aXABB\\ A& \to & aAB|b\\ B& \to & b\\ X& \to & a\end{array}$$

---

Q2.

(10 points) Convert the following grammar into CNF and GNF.

(a).

$$\begin{array}{ll}S& \to baAB\\ A& \to bAB|\lambda \\ B& \to BAa|A|\lambda \end{array}$$

Solution
First eliminate

$\lambda$-productions. This gives

$$\begin{array}{l}S\to baAB|baA|baB|ba,\\ A\to bAB|bA|bB|b,\\ B\to BAa|Ba|Aa|A|a.\end{array}$$
There is a unit-production,

$B\to A$, so we must remove it from the grammar and get

$$\begin{array}{l}S\to baAB|baA|baB|ba,\\ A\to bAB|bA|bB|b,\\ B\to BAa|Ba|Aa|bAB|bA|bB|b|a.\end{array}$$

$(i)$ CNF
We can now apply the construction and get

$$\begin{array}{l}S\to V_b{V}_{a}AB|V_b{V}_{a}A|V_b{V}_{a}B|V_b{V}_a,\\ A\to V_{b}AB|V_{b}A|V_{b}B|b,\\ B\to BA{V}_a|B{V}_a|A{V}_a|V_{b}AB|V_{b}A|V_{b}B|b|a,\end{array}$$
and

$$\begin{array}{l}S\to V_c{V}_d|V_{c}A|V_{c}B|V_b{V}_a,\\ A\to V_b{V}_d|V_{b}A|V_{b}B|b,\\ B\to V_e{V}_a|B{V}_a|A{V}_a|V_b{V}_d|V_{b}A|V_{b}B|b|a,\\ V_a\to a,\\ V_b\to b,\\ V_c\to V_b{V}_a,\\ V_d\to AB,\\ V_e\to BA,\end{array}$$

$(ii)$ GNF

---

(b).

$$\begin{array}{ll}S& \to AB|aB\\ A& \to abb|\lambda \\ B& \to bbA\end{array}$$

Solution
First eliminate

$\lambda$-productions. This gives

$$\begin{array}{l}S\to AB|B|aB,\\ A\to aab,\\ B\to bbA|bb.\end{array}$$
This has introduced a unit-production, which is not acceptable in the construction of using Theorem

$6.6$.

$$\begin{array}{l}S\to AB|bbA|aB|bb,\\ A\to aab,\\ B\to bbA|bb.\end{array}$$

$(i)$ CNF
We can now apply the construction and get

$$\begin{array}{l}S\to AB|V_b{V}_{b}A|V_{a}B|V_b{V}_b,\\ A\to V_a{V}_a{V}_b,\\ B\to V_b{V}_{b}A|V_b{V}_b,\end{array}$$
and

$$\begin{array}{l}S\to AB|V_{c}A|V_{a}B|V_b{V}_b,\\ A\to V_d{V}_b,\\ B\to V_{c}A|V_b{V}_b,\\ V_c\to V_b{V}_b,\\ V_d\to V_a{V}_b,\\ V_a\to a,\\ V_b\to b.\end{array}$$

$(ii)$ GNF
By introducing productions

$V_b$, we can convert the grammar into Greibach normal form.

$$\begin{array}{ll}S& \to a{V}_b{V}_{b}B|b{V}_{b}A|aB,\\ A& \to a{V}_b{V}_b,\\ B& \to b{V}_{b}A|b{V}_b,\\ V_b& \to b.\end{array}$$

---

Q3.

(15 points) Use the CYK algorithm to determine whether the string

$aabba$ is in the language generated by the grammar

$$\begin{array}{ll}S& \to AB\\ A& \to BB|a\\ B& \to AB|b\end{array}$$

Solution
For the string

$aabba$.
Let

$w_{i,j}=a_i\dots a_j$ be a substring of

$w=aabba$ and also let

$V_{i,j}=\{A:A\to XY$,

$X\Rightarrow w_{i,k}$ and

$Y\Rightarrow w_{k+1,j}\}$. Then, we compute

$V_{ij}$ for

$1\le i\le j\le 5$. If

$w$ in

$L(G)$,

$S\in V_{1,5}$, otherwise

$S\notin V_{1,5}$.

Step 1.

$V_{1,1}=\{A\}$,

$V_{2,2}=\{A\}$,

$V_{3,3}=\{B\}$,

$V_{4,4}=\{B\}$,

$V_{5,5}=\{A\}$.

Step 2.

$V_{1,2}=\mathrm{\varnothing }$,

$V_{2,3}=\{S,B\}$,

$V_{3,4}=\{A\}$,

$V_{4,5}=\mathrm{\varnothing }$.

Step 3.

$V_{1,3}=\{S,B\}$,

$V_{2,4}=\{A\}$,

$V_{3,5}=\{B\}$

Step 4.

$V_{1,4}=\{A\}$,

$V_{2,5}=\{S,B\}$

Step 5.

$V_{1,5}=\{S,B\}$

Since

$S\in V_{1,5}$, the string

$aabba$ is in the language.

---

Q4.

(15 points) Construct npda's that accept the following languages

$L=\{a^n{b}^{n+m}{c}^m:n\ge 0,m\ge 1\}$ on

$\mathrm{\Sigma }=\{a,b,c\}$

Solution
Start with an initial

$z$ in the stack. Put a mark a on the stack when input alphabet is an a, consume a mark a when input is a

$b$. When all

$a$'s in the stack are consumed, put a mark

$b$ to the stack when input is a

$b$. After input becomes

$c$, eliminate a mark on the stack. The string will be accepted if the stack has only

$z$ left when the input is completed.

---

Q5.

(20 points) Show that the following languages on

$\mathrm{\Sigma }=\{a,b,c\}$ are not context free:

$(a).L=\{a^n{b}^j{c}^k:k=jn\}$

Solution
The language is context-free. A grammar for it is

$$\begin{array}{l}S\to aSb|S_1,\\ S_1\to b{S}_{1}a|\lambda .\end{array}$$

---

$(b).L=\{w:n_a(w)=n_b(w)\ast n_c(w)\}$

Solution
Given

$m$, we pick

$w=a^{m^2}{b}^m{c}^m$ which is in

$L$. It is easy to see that the only chance for the adversary to win is to choose

$v=a^k,y=b^l$ for

$k\ne 0,l\ne 0$. Then the pumped string is

$w_i=a^{m^2+(i-1)k}{b}^{m+(i-1)l}{c}^m.$ However, for

$w_0=a^{m^2-k}{b}^{m-l}{c}^m$, we see immediately that

$$(m-l)m=m^2-ml<m^2-k.$$
That means

$w_0\notin L$, so

$L$ is not context-free.

---

Q6.

(10 points) Construct Turing machines that will accept the following language

$L=\{a^n{b}^m:n\ge 2,n=m\}$ on

$\{a,b\}$

Solution
A transition graph with

$F=\{q_6\}$ is

---

Q7.

(20 points) Design Turing machines to compute the following functions

$f(x)=$ the largest integer less than or equal to

$x/2$ for

$x$ and

$y$ positive integers represented by unary.

Solution
Start by removing the leftmost

$1$, then move to the rightmost

$1$ and mark it by replacing it with

$x$. The read-write head then moves back to the leftmost

$1$ and repeat the above process until there are no more

$1$'s. Finally, we replace all the marked

$x$'s by

$1$'s to complete the computation. The transition graph of a Turing machine with

$F=\{q_6\}$ is given below.