---
tags: Formal Language 2019
title: HW-04
---

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

# FORMAL Language 2019 HW-4
## reference : others
## Problem 1
Construct a dfa 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**== It is straightforward to construct a nfa for the given grammar with a $\lambda$-transition from state $S$ to $A$. Then apply the procdure nfa-to-dfa.


---
## Problem 2
Construct a left-linear grammar for the languages in Problem 1.

==**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}
$$

---
## Problem 3
Find regular grammars for the following languages on $\{a,b\}$.
**A.** $L=\{w: n_a(w)$ and $n_b(w)$ are both even $\}$

**Solution:** Using mnemonic label to denote even-odd paris of a and b for each vertex in a transition graph. We get a dfa for the problem
From the dfa, an answer is

$$
\begin{array}{lll}
EE & \rightarrow & aOE|bEO|\lambda,\\
OE & \rightarrow & aEE|bOO,\\
EO & \rightarrow & aOO|bEE,\\
OO & \rightarrow & aEO|bOE.\\
\end{array}
$$

---
**B.** $L=\{w:(n_a(w)-n_b(w))$ mod $3\ne 1\}$

**Solution:** A dfa has the same diagram as \(c\) except that $q_0,q_3,q_4$ are final states but $q_1,q_2$ are not. A solution is

$$
\begin{array}{lll}
q_0 & \rightarrow & aq_1|bq_2|\lambda,\\
q_1 & \rightarrow & aq_3|bq_0,\\
q_2 & \rightarrow & aq_0|bq_4,\\
q_3 & \rightarrow & aq_0|bq_1|\lambda,\\
q_4 & \rightarrow & aq_2|bq_0|\lambda.\\
\end{array}
$$

---
**C.** $L=\{w:(n_a(w)-n_b(w))$ mod $3=1\}$

**Solution:** Base on the dfa of Exercise 7(e) of Section 2.1, a dfa for this problem is
An answer is

$$
\begin{array}{lll}
q_0 & \rightarrow & aq_1|bq_2,\\
q_1 & \rightarrow & aq_3|bq_0|\lambda,\\
q_2 & \rightarrow & aq_0|bq_4|\lambda,\\
q_3 & \rightarrow & aq_0|bq_1,\\
q_4 & \rightarrow & aq_2|bq_0.\\
\end{array}
$$

---
**D.** $L=\{w:|n_a(w)-n_b(w)|$ is odd $\}$

**Solution:** Split the problem into two parts : $n_a(w)$ is even but $n_b(w)$ is odd and $n_a(w)$ is odd but $n_b(w)$ is even. A dfa is then the same as that of part (b) except that the final states are now $OE$ and $EO$ instead of $EE$. A grammar is

$$
\begin{array}{lll}
EE & \rightarrow & aOE|bEO,\\
OE & \rightarrow & aEE|bOO|\lambda,\\
EO & \rightarrow & aOO|bEE|\lambda,\\
OO & \rightarrow & aEO|bOE.\\
\end{array}
$$

---
## Problem 4
Find regular grammar that generates the language
$L=\{w\in \{a,b\}^*: n_a(w)+3n_b(w)$ is odd $\}$

**Solution:** Note that $3n_b(w) \mbox{ mod } 2 = n_b(w) \mbox{ mod } 2$ simple approach is to draw a nfa using mnemonic label for the vertices. Using the construction given by Theorem $3.4$, an answer is

$$
\begin{array}{lll}
EE & \rightarrow & aOE|bEO,\\
OE & \rightarrow & aEE|\lambda,\\
EO & \rightarrow & bEE|\lambda.\\
\end{array}
$$

---
## Problem 5
Determine whether or not the following languages on $\Sigma =\{a\}$ are regular:

**A.** $L=\{a^n:n$ is not a prime number $\}.$

**Solution:** Assume $L$ is regular, then we known regularity is closed under complement. Therefore,

:::info
$$
\overline L = \{a^n : n \ge 2 ,\mbox{ is a prime number} \}
$$
:::

must be regular. However, it contradicts what we shown in (a). So $L$ is not regular.

---
**B.** $L=\{a^n:n=2^k$ for some $k\ge 0\}.$

**Solution:** Suppose $L$ is regular and m is given. Let $p$ be the smallest number such that $2^p > m$. Then we pick $w = a^{2^p}$ in $L$. The string $y$ must then be $a^k$ for some $1 \le k \le m$ and the pumped strings will be

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

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

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

**Solution:** Suppose $L$ is regular and $m$ is given. Let $p, q$ be the smallest prime numbers such that $pq \ge m$. Then we pick $w = a^{pq}$ in $L$. The string $y$ must then be $a^k$ for some $1 \le k \le m$ and the pumped strings will be

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

However, $w_{pq+1} = a^{pq+pqk} = a^{pq(1+k)} \notin L$, because $pq(1 + k)$ is no longer a product of two prime numbers. Therefore $L$ is not regular.

---
## Problem 6
Show that the language $L=\{a^{n!}:n\ge 1\}$ is not regular.

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

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

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

---
## Problem 7
Is the following language regular? $\{w_1cw_2:w_1,w_2\in \{a,b\}^*,w_1\ne w_2\}$

**Solution:** Let us consider
$$\overline L \cap L((a + b)^*c(a + b)^*) = \{w_1cw_2 : w_1 = w_2\}.$$
Suppose $\overline L \cap L((a + b)^*c(a + b)^*)$ is regular and $m$ is given. We pick $w = a^mca^m$ which is in $\overline L\cap L((a+b^*c(a+b)^*)$. The string $y$ must then be $a^k$ for some $1 \le k \le m$ and the pumped strings will be

:::info
$$
wi = a^{m+(i-1)k}ca^m \in L \cap L((a + b)^*c(a + b)^*),\mbox{ for }i = 0, 1,...
$$
:::

However, $w_0 = a^{m-k}ca^m \notin \overline L \cap L((a + b)^*c(a + b)^*)$.Therefore $\overline L \cap L((a + b)^*c(a + b)^*)$ is not regular. However, since $L((a + b)^*c(a + b)^*)$ is regular, $\overline L$ must be nonregular. Because closure of regularity under complement, $L$ can not regular.

---
## Problem 8
Show that the language generated by the grammar $S \rightarrow aSS | b$ is not regular.

**Solution:** Let us look at all the following three sentential forms from an one step derivation:

$$
\begin{array}{lll}
S \Rightarrow aSS \Rightarrow abS,\\
S \Rightarrow aSS \Rightarrow aSb,\\
S \Rightarrow aSS \Rightarrow aaSSS.\\
\end{array}
$$

Notice that both the given productions and the above sential forms have a common property. That is the sum of numbers of $b$'s and $S$'s is always one larger than the number of $a$'s. Hence we know immediately that this property must be retained in any sentential form. Moreover, in order to get a sentence, we must eventually substitute all the $S$'s by $b$'s into a sentential form. Also note that there are always more $b$'s and $S$'s on the right side of any symbol $a$. So the language is

:::info
$$
L = w \in \{a,b^+ : n_b(w) = n_a(w)+1; n_b(v) > n_a(v),\\
\mbox{ for any suffix }v\mbox{ of }w\}.
$$
:::

It is a relative routine task to slow $L$ is not regular by picking $w = a^mb^{m+1}$ for the argument using in the pumping lemma.