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

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

# FORMAL Language 2019 HW-5
## reference : others

## Problem 1
Prove or disprove the following statement: If $L_1$ and $L_2$ are nonregular languages, then $L_1\cup L_2$ is also nonregular.

**Solution:** The proposition is false. As a counterexample, take $L_1 = \{a^nb^m : n \le m\}$ and $L_2 = \{a^nb^m : n > m\}$, both of which are non-regular. But $L1 \cup L2 = L (a^*b^*)$, which is regular.

---
## Problem 2
The $nor$ of two languages is
$$nor(L_1,L_2)=\{w:w\notin L_1 \mbox{ and } w\notin L_2\}.$$
Show that the family of regular languages is closed under ${\it nor}$ operation.

**Solution:** Notice that
$$nor (L1, L2) = \overline {L1 \cup L2}.$$
The result then follows from closure under intersection and complementation.

---
## Problem 3
Define the complementary of $({\it cor})$ of two languages by
$$cor(L_1,L_2)=\{w:w\in \overline{L_1} \mbox{ or } w\in \overline{L_2}\}.$$
Show that the family of regular languages is closed under ${\it cor}$ operation.

**Solution:** Notice that
$$cor (L1, L2) = \overline {L1} \cup \overline {L2}.$$
The result then follows from closure under union and complementation.

---
## Problem 4
Consider the language $L=\{a^n:n$ is not a perfect square$\}.$

**A.** Show that this language is not regular by applying the pumping lemma directly.

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

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

However, if we choose $i = ((m!)^2m(m + 2) - 1)/k + 1$, then it is not difficult to show that $(m!)^2 + 1 + (i - 1)k = ((m+ 1)!)^2$. That means such a $w_i$ is not in $L$. Therefore $L$ is not regular.

---
**B.** Then show the same thing by using the closure properties of regular languages.

**Solution:** Problem $2$ shows that the complement of $L$ is not regular. Therefore $L$ must not be regular.

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

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

**Solution:** Suppose $L$ is regular and $m$ is given. Let $p$ be the smallest prime number such that $p \ge m$. Then we pick $w = a^p$ in $L$. The string $y$ must then be $a^k$ and the pumped strings will be

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

However, $w_{p+1} = a^{p+pk} = a^{p(1+k)} \notin L$. Therefore $L$ is not regular.

---
**B.** $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.

---
**C.** $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.

---
## Problem 6
Let $L_1$ and $L_2$ be regular language. Is the language $L=\{w:w\in L_1, w^R\in L_2\}$ necessarily regular ?

**Solution:** Yes, $L$ is regular. We see this from $L = L_1 \cap L^R_2$ and the known closures for regular languages.

---
## Problem 7
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
$$S1 \ominus S2 = (S1 \cup S2) - (S1 \cap S2).$$
The result then follows from closure under union, intersection and difference.

---
## Problem 8
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$.

---
## Problem 9
For a string $a_1a_2\cdots a_n$ define the operation *shift* as $shift(a_1a_2\cdots a_n)=a_2a_3\cdots a_na_1$.
From this, we can define the operation on a language as $shift(L)=\{v:v=shift(w)$ for some $w\in L\}$.
Show that regularity is preserved under the $shift$ operation.

**Solution:** Suppose the graph for $L$ looks like


We replace this with


If $q_0$ has several outgoing edges, we create a sub-automaton for each, giving us an nfa with multiple initial states.

---
## Problem 10
Let $G_1$ and $G_2$ be two regular grammars. Show how one can derive regular grammars for the following lanuages

A. $L(G_1)\cup L(G_2)$
B. $L(G_1)L(G_2)$
C. $L(G_1)^*$

**Solution:** Suppose $G_1 = (V_1, T, S_1, P_1)$ and $G_2 = (V_2, T, S_2, P_2)$. Without loss of generality, we can assume that $V_1$ and $V_2$ are disjoint. Combine the two grammars and

**A.** Make $S$ the new start symbol and add productions $S \rightarrow S1|S2$.
**B.** In $P_1$, replace every production of the form $A \rightarrow x$, with $A \in V_1$ and $x \in T^*$, by $A \rightarrow xS_2$.
**C.** In $P_1$, replace every production of the form $A \rightarrow x$, with $A \in V_1$, and $x \in T^*$, by $A \rightarrow xS_1, S_1 \rightarrow \lambda$.