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

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

# FORMAL Language 2019 HW-1
Scope of the homework (ch2-1 ~ ch2-2)
## Problem 1
Give dfa's for the languages

**A.** $L=\{ab^4wb^2: w\in \{a,b\}^*\}$

==**Solution**== The key is that any string that can be accept by the solution dfa must consist $ab^4$ at the begining and two $b$'s at the end.
The first requirement is straightforward, and the second requirement is solved between states $q_5$ to $q_7$.

---
**B.** $L=\{ab^na^m:n\ge 3, m\ge 2\}$

==**Solution**==

---
**C.** $L=\{w_1abbw_2: w_1\in \{a,b\}^*, w_2\in\{a,b\}^*\}$

==**Solution**==

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

}

---
**D.** $L=\{ba^n: n\ge 1, n\ne 4\}$

==**Solution**==
The dfa must have final states corresponding to one $a$, two, three,
five, and more $a$'s but not four $a$'s as shown below.

---
## Problem 2
With $\Sigma = \{a,b \}$, give a dfa for $L=\{w_1aw_2: |w_1|\ge 3, |w_2|\le 4\}$

==**Solution**== The dfa will accept any string of length greater than four
with no more than four consecutive $b$'s after the last $a$.

---
## Problem 3
Find dfa's for the following languages on $\Sigma \{a,b\}$.
**A.** $L=\{w:|w| \mbox{ mod } 3\ne 0\}$.

**Solution:** Use states labeled with $|w| \mbox{ mod } 3$.

---
**B.** $L=\{w:|w| \mbox{ mod } 5=0\}$.

**Solution:** Use states labeled with $|w| \mbox{ mod } 5$.

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

**Solution:** Use states labeled with $n_a(w) \mbox{ mod } 3$.

---
**D.** $L=\{w:n_a(w) \mbox{ mod } 3 < n_b(w) \mbox{ mod } 3\}$

**Solution:** For this we use nine states, with the first part of each labeled $n_a(w)
\mbox{ mod } 3$, the second part $n_b(w) \mbox{ mod } 3$.

---
**E.** $L=\{w:(n_a(w)-n_b(w)) \mbox{ mod } 3 =0\}$

**Solution:** We use states labeled by two digit numbers, with the first part of
each labeled $n_a(w) \mbox{ mod } 3$, the second part, $n_b(w) \mbox{ mod } 3$.

---
**F.** $L=\{w:(n_a(w)+2n_b(w)) \mbox{ mod } 3 < 1\}$

**Solution:** Use the states labeled with $n_a(w) + 2n_b(w) \mbox{ mod } 3$.

---
**G.** $L=\{w:|w| \mbox{ mod } 3 = 0, |w|\ne 3\}$

**Solution:** Use states labeled with $|w| = 0, 1, 2, 3, ..., 6$.

---
## Problem 4
Design n nfa with no more than five states for the set $\{abab^n:n\ge 0\}\cup \{aba^n:n\ge 0\}$.

**Solution:**