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

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

# FORMAL Language 2019 HW-3
## Problem 1
Find a regular expression for the set $\{a^nb^m: (n+m)$ is odd $\}$.

==**Solution**== Either the number of $a$'s is odd and the number of $b$'s is even or vise versa. A regular expression is $(aa)^*(a + b)(bb)^*$.

---
## Problem 2
Give regular expressions for the following languages.
**1.** $L_1=\{a^nb^m: n\ge 3, m\le 4\}$

==**Solution**== Separate into cases $m=0,1,2, 3,4$. Generate $3$ or more $a$'s, followed by the requisite number of b's. A regular expression for $L_1$ is $aaaa^*(\lambda+b+bb+bbb+bbbb)$.

---
**2.** $L_2=\{a^nb^m:n<4, m\le 4\}$

==**Solution**== Separate into cases $m=0,1,2,3$ and $n=0,1,2,3,4$. A regular expression for $L_2$ is $(\lambda+a+aa+aaa)(\lambda+b+bb+bbb+bbbb)$.

---
**3.** The complement of $L_1$

==**Solution**== A string is not in $L_1$ if it is of the form $a^nb^m$, with either $n<3$ or $m>4$, but this does not completely describe $L_1$. We must also consider the case where $a\ b$ is followed by an $a$.
$$(\lambda+a+aa)b^*+a^*bbbbbb^*+(a+b)^*ba(a+b)^*.$$

---
**4.** The complement of $L_2$

==**Solution**== A string that is not in $L_2$ if it is of the form $a^nb^m$, with either $n\geq4$ or $m>4$, but this does not completely describe $L_2$. We must also consider the case where $a\ b$ is followed by an $a$.
$$aaaaa^*b^*+a^*bbbbbb^*+(a+b)^*ba(a+b)^*.$$

---
## Problem 3
Find a regular expression for $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}
$$

---
## Problem 4
Find dfa's that accept the following languages.
**A.** $L=L(ab^*a^*)\cup L((ab)^*ba).$

==**Solution**== Start with


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


---
**B.** $L=L(ab^*a^*)\cap L((b)^*ab).$

==**Solution**== Note that $L(ab^*a) \cap L ((b)^*ab)=\{ab\}$. A dfa is trivial.

---
## Problem 5
What language is accepted by the following generalized transition graph ?

digraph problem5 {
	rankdir=LR;
	size="8,5"
	node [shape = doublecircle]; q2;
	node [shape = circle];
	q0 -> q0 [ label = "a" ];
	q0 -> q1 [ label = "a" ];
	q0 -> q2 [ label = "a*+b+c" ];
	q1 -> q1 [ label = "a+b" ];
	q1 -> q2 [ label = "a+b" ];
	q2 -> q2 [ label = "a+b*" ];
}

---
## Problem 6
Construct a dfa that accepteds the language generated by the grammar
:::info
$$
\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 7
Find a regular grammar that generates the language $L(aa^*(ab+a)^*)$.

==**Solution**==
$$
\begin{array}{lll}
S & \rightarrow & aA,\\
A & \rightarrow & aA|B,\\
B & \rightarrow & abB|aB|\lambda.\\
\end{array}
$$

---
## Problem 8
Find a regular grammar for the language $L=\{a^nb^m:n+m$ is odd$\}$.

==**Solution**== Draw an nfa using mnemonic label for the problem Using the construction given by Theorem 3.4, an answer is
$$
\begin{array}{lll}
EE & \rightarrow & aOE|bEO,\\
OE & \rightarrow & aEE|bOO|\lambda,\\
OO & \rightarrow & bEO,\\
EO & \rightarrow & bOO|\lambda.\\
\end{array}
$$