---
tags: Formal Language
title: Home Work 1
---
# FORMAL Language 2021
---
>[TOC]
---
## HW_1 : Scope of the homework (ch2-1 ~ ch2-2)
:::danger
### homework : 1A 1B 2 3F 4 6
:::
### reference : others
:::danger
### submit on next week class
:::
### Problem 1
Give dfa's for the languages
A. $L=\{ab^4wb^2: w\in \{a,b\}^*\}$
B. $L=\{ab^na^m:n\ge 3, m\ge 2\}$
Give dfa’s for the languages
C. $L=\{w_1abbw_2: w_1\in \{a,b\}^*, w_2\in\{a,b\}^*\}$
D. $L=\{ba^n: n\ge 1, n\ne 4\}$
:::danger
1. $\{a,b\}^*$ is denoted the set of all possible strings constructed by $\{a,b\}$
2. For $a\in \Sigma$, $a^n=aaaa\cdots a$, $|a^n|=n$
:::

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

### Problem 3
Find dfa's for the following languages on $\Sigma = \{a,b\}$.
A. $L=\{w:|w| \mbox{ mod } 3\ne 0\}$.
B. $L=\{w:|w| \mbox{ mod } 5=0\}$.
C. $L=\{w:n_a(w) \mbox{ mod } 3 < 1\}$.
D. $L=\{w:n_a(w) \mbox{ mod } 3 < n_b(w) \mbox{ mod } 3\}$
E. $L=\{w:(n_a(w)-n_b(w)) \mbox{ mod } 3 =0\}$
F. $L=\{w:(n_a(w)+2n_b(w)) \mbox{ mod } 3 < 1\}$
G. $L=\{w:|w| \mbox{ mod } 3 = 0, |w|\ne 5\}$
:::danger
For any string $w$ and $a\in \Sigma$, $n_a(w)$ is denoted the number of $a$ char in the string $w$.
:::
### Problem 4
Design an nfa with no more than five states for the set $\{abab^n:n\ge 0\}\cup \{aba^n:n\ge 0\}$.

### Problem 5
Find an nfa with three states that accepts the language \\
$L=\{a^n:n\ge 1\}\cup \{b^ma^k:m\ge 0, k\ge 0\}$.
Do you think the language in part (a) can be accepted by an nfa with fewer than three states ?

### Problem 6
Let $L$ be the language accepted by the nfa in Figure 2.8.
Find an nfa that accepts $L\cup \{a^5\}$

### Problem 7
Find an nfa for $L^*$, where $L$ is the language in (6).
:::danger
1. Notice: the definition $L^* = L^0\cup L^1\cup L^2\cup L^3\cdots$. and $L^n = L\cdot L\cdot L\cdots L^n$
and $L \cdot L = \{xy: x\in L$ and $y\in L\}$.
For example. if $L = \{ awb: w$ is any string of $a,b\}$, $L^2=L\cdot L=\{axbayb: x,y\in L\}$

2. For any language $L$, $L^0=\{\lambda\}$
:::

### figure
### answer (upload on next week)
- 1_a
- 1_b 
- 1_d 
- 2 3_a

- 3_bcd
- 3_ef
- 3g
- 4
- 5
- 6
- 7