---
tags: Formal Language 2019
title: Mid-term
---

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

# FORMAL Language 2019 Mid-term
## Q1.
(10 points) Design n nfa with no more than five states for the set $\{abab^n : n\ge0\} \cup \{aba^n : n\ge0\}.$

**Solution:**

---
**Another solution:**

digraph problem5 {
	rankdir=LR;
	size="8,5"
    node [shape = none]; ""
	node [shape = doublecircle]; "   " "    ";
	node [shape = circle];
    
    "" -> " "
    " " -> "  " [ label = "a" ];
    "  " -> "   " [ label = "b" ];
    "   " -> "   " [ label = "a" ];
    "   " -> "    " [ label = "a" ];
    "    " -> "    " [ label = "b" ];
}

---
## Q2.
(10 points) Convert the nfa defined by
$$
\begin{array}{lll}
\delta(q_0,a)=\{q_0,q_1\}\\
\delta(q_1,b)=\{q_1,q_2\}\\
\delta(q_2,a)=\{q_2\}\\
\delta(q_1,\lambda)=\{q_1,q_2\}\\
\end{array}
$$
with initial state $q_0$ and final state $q_2$ into an equivalent dfa.

**Solution:**


---
## Q3.
(15 points) Find the minimal dfa that accept
$L(abb)^* \cdot L(a^*bb^*)$

**Solution:** Start with


Then use the nfa-to-dfa algorithm and procedures $mark$ and $reduce$ in Chapter 2 to get the minimal dfa


---
## Q4.
(15 points ) Construct a left-linear grammar that accepts the language generated by the grammar
$$
\begin{array}{lll}
S & \rightarrow & abS|A,\\
A & \rightarrow & baB,\\
B & \rightarrow & aA|bb.\\
\end{array}
$$

**Solution:** The language in Question 4 is $L=\{(ab)^*ba(aba)^*bb\}$. A left-linear grammar can be constructed by taken the regular expression inreverse order.

$$
\begin{array}{lll}
S & \rightarrow & Abb,\\
A & \rightarrow & Aaba|B,\\
B & \rightarrow &Cba,\\
C & \rightarrow &Cab|\lambda.\\
\end{array}
$$

---
**Another solution:**

$$
\begin{array}{lll}
S & \rightarrow & Abb,\\
A & \rightarrow & Aaba|Bba,\\
B & \rightarrow & Bab|\lambda,\\
\end{array}
$$

---
## Q5.
(20 points) Determine whether or not the following languages on $\Sigma =\{a\}$ are regular:

**A.** $L=\{a^n:n=k^3$ for some $k\ge 0\}.$

**Solution:** Suppose $L$ is regular and $m$ is given. We pick $w = a^{m^3}$ in $L$. The string $y$ must then be $a^k$ and the pumped strings will be

:::info
$$
w_i = a^{m^3+(i-1)k} \in L,\mbox{ for }i = 0, 1,...
$$
:::

However, $w_2 = a^{m^3+k} \notin L$, because that $m^3 + k < m^3 + m < (m + 1)^3$. Therefore $L$ is not regular.

---
**B.** $L=\{a^n:n$ is either prime or the product of two or more prime numbers $\}$

**Solution:** Since we know any positive integer that is not a prime number must be a product of two or more prime numbers, therefore $L = \{a^n : n \ge 0\}$. That is, $L = L(a^*)$ is regular.

---
## Q6.
(15 points) The *symmetric difference* of two sets $S_1$ and $S_2$ is defined as $S_1 \ominus S_2=\{x: x\in S_1$ or $x\in S_2$, but $x$ is not in both $S_1$ and $S_2\}$
Show that the family of regular languages is closed under symmetric difference.

**Solution:** Notice that
:::info
$$S1 \ominus S2 = (S1 \cup S2) - (S1 \cap S2).$$
:::
The result then follows from closure under union, intersection and difference.

---
## Q7.
(15 points) The *tail* of a language is defined as the set of all suffixes of its strings, that is $tail(L)=\{y: xy\in L$ for some $x\in \Sigma^*\}$
Show that if $L$ is regular, so is $tail(L)$.

**Solution:** Find the set $Q_t$ for all states q such that $\delta (q,w) \in F$ for some $w$. Then create a new initial state and add a $\lambda$-transition from it to all elements of $Q_t$.