---
tags: Formal Language 2019
title: Final
---

<style>
img {
margin: auto;
display: block;
}
</style>

# FORMAL Language 2019 Final
## Q1.
(10 points) Find an s-grammar for the language $L = \{a^nb^{n+1} : n \ge 3\}$.

==**Solution**==
$$
\begin{array}{ll}
S & \rightarrow & aS_1B\\
S_1 & \rightarrow & aXABB\\
A & \rightarrow & aAB|b\\
B & \rightarrow & b\\
X & \rightarrow & a\\
\end{array}
$$

---
## Q2.
(10 points) Convert the following grammar into CNF and GNF.
:::success
(a). $$
\begin{array}{ll}
S & \rightarrow baAB\\
A & \rightarrow bAB|\lambda \\
B & \rightarrow BAa|A|\lambda
\end{array}
$$
:::

==**Solution**==
First eliminate $\lambda$-productions. This gives
$$
\begin{array}{lll}
S \rightarrow baAB|baA|baB|ba,\\
A \rightarrow bAB|bA|bB|b,\\
B \rightarrow BAa|Ba|Aa|A|a.\\
\end{array}
$$
There is a unit-production, $B \rightarrow A$, so we must remove it from the grammar and get
$$
\begin{array}{lll}
S \rightarrow baAB|baA|baB|ba,\\
A \rightarrow bAB|bA|bB|b,\\
B \rightarrow BAa|Ba|Aa|bAB|bA|bB|b|a.\\
\end{array}
$$

$(i)$ CNF
We can now apply the construction and get
$$
\begin{array}{lll}
S \rightarrow V_bV_aAB|V_bV_aA|V_bV_aB|V_bV_a,\\
A \rightarrow V_bAB|V_bA|V_bB|b,\\
B \rightarrow BAV_a|BV_a|AV_a|V_bAB|V_bA|V_bB|b|a,\\
\end{array}
$$
and
$$
\begin{array}{lll}
S \rightarrow V_cV_d|V_cA|V_cB|V_bV _a,\\
A \rightarrow V_bV_d|V_bA|V_bB|b,\\
B \rightarrow V_eV_a|BV_a|AV_a|V_bV_d|V_bA|V_bB|b|a,\\
V_a \rightarrow a,\\
V_b \rightarrow b,\\
V_c \rightarrow V_bV_a,\\
V_d \rightarrow AB,\\
V_e \rightarrow BA,\\
\end{array}
$$

$(ii)$ GNF

---

:::info
(b). $$
\begin{array}{ll}
S & \rightarrow AB|aB\\
A & \rightarrow abb|\lambda \\
B & \rightarrow bbA
\end{array}
$$
:::

==**Solution**==
First eliminate $\lambda$-productions. This gives
$$
\begin{array}{ll}
S \rightarrow AB|B|aB,\\
A \rightarrow aab,\\
B \rightarrow bbA|bb.\\
\end{array}
$$
This has introduced a unit-production, which is not acceptable in the construction of using Theorem $6.6$.
$$
\begin{array}{ll}
S \rightarrow AB|bbA|aB|bb,\\
A \rightarrow aab,\\
B \rightarrow bbA|bb.\\
\end{array}
$$

$(i)$ CNF
We can now apply the construction and get
$$
\begin{array}{ll}
S \rightarrow AB|V_bV_bA|V_aB|V_bV_b,\\
A \rightarrow V_aV_aV_b,\\
B \rightarrow V_bV_bA|V_bV_b,\\
\end{array}
$$
and
$$
\begin{array}{ll}
S \rightarrow AB|V_cA|V_aB|V_bV_b,\\
A \rightarrow V_dV_b,\\
B \rightarrow V_cA|V_bV_b,\\
V_c \rightarrow V_bV_b,\\
V_d \rightarrow V_aV_b,\\
V_a \rightarrow a,\\
V_b \rightarrow b.\\
\end{array}
$$

$(ii)$ GNF
By introducing productions $V_b$, we can convert the grammar into Greibach normal form.
$$
\begin{array}{ll}
S & \rightarrow aV_bV_bB|bV_bA|aB,\\
A & \rightarrow aV_bV_b,\\
B & \rightarrow bV_bA|bV_b,\\
V_b & \rightarrow 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 & \rightarrow AB\\
A & \rightarrow BB|a \\
B & \rightarrow AB|b\\
\end{array}
$$

==**Solution**==
For the string $aabba$.
Let $w_{i,j}=a_i\ldots a_j$ be a substring of $w=aabba$ and also let $V_{i,j}=\{A:A\rightarrow 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}=\emptyset$, $V_{2,3}=\{S,B\}$, $V_{3,4}=\{A\}$, $V_{4,5}=\emptyset$.

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^nb^{n+m}c^m:n\ge 0,m\ge 1\}$ on $\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 $\Sigma =\{a,b,c\}$ are not context free:
$(a).L=\{a^nb^jc^k:k=jn\}$

==**Solution**==
The language is context-free. A grammar for it is
$$
\begin{array}{ll}
S \rightarrow aSb|S_1,\\
S_1 \rightarrow bS_1a|\lambda.\\
\end{array}
$$

---

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

==**Solution**==
Given $m$, we pick $w = a^{m^2}b^mc^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^nb^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.