# CS374/ECE374 Midterm1 Fodder Answers
This document is used to summarize fodder answers for exam review and discussion. All answers are edited by students, and their accuracy is affected by the abilities of the answer providers. They are only intended as reference materials for review.

This document is kept public and welcomes participation in editing and improvement.

Please don't edit existing answers, **use comment for any doubtful solutions**, until the change is confirmed to be correct.

Also you can subscribe the document after signed in. Then you can get notification once it is updated.
## 1. Induction on Strings
1.
2.
3.
4.
5.
6.
7.
## 2. Regular expressions
1. $(\varepsilon+0+1)(\varepsilon+0+1)(\varepsilon+0+1)$
2. $\varepsilon+0+1(0+1)^*+01+00(0+1)^*+011(0+1)^*+010(0+1)(0+1)^*$
The idea behind that is to include all the strings by the prefix.
If $|w|=0$, it is empty string $\varepsilon$.
If $|w|=1$, both $0$ and $1x$ are not $010$.
If $|w|=2$, both $01$ and $00x$ are not $010$.
If $|w|=3$, strings starting with $011$ satisfy the requirements.
All strings $|w|>4$ cannot be $010$.
3. $(0+1)^*010$
4. $\varepsilon+0+1(0+1)^*+01+00(0+1)^*+011(0+1)^*$
Same as 2.2, but removing all the strings of $010w$.
5. $(0+1)^*010(0+1)^*$
6. $(1+00^*11)^*(\varepsilon +00^*+00^*1)$
7. $(0+1)^*0(0+1)^*1(0+1)^*0(0+1)^*$
8. $1^* 0^* 1^*$
9. $(0+1)^*(01+10)(0+1)^*$
10. $11^*00^*+00^*11^*$
11. $(\varepsilon+1)(01)^*1^*+(\varepsilon+0)(10)^*0^*$

> [name=Guest Hines]
> Is $(1 + 01)^*0^* + (0 + 10)^*1^*$ acceptable for 2.11?
> [name=Guest Barnes]
> No. You can make 110 easily with the first part.
> [name=Guest Barnes]
> I think $(\varepsilon + 1)(01)^*(\varepsilon + 0^*+1^*)$ is valid though. No need to break it up into (01) and (10) in the first answer I don't think.
12. $(0+1)^*(01+10)(0+1)^*$
13. $11^*00^*+00^*11^*$
14. $(0+1)^*(110+100^*1+011)(0+1)^*$
15. $111^*+1^*0(0+1)^*$
16. $111^*+0^*(10+0+01)0^*$
17. $1^*(001^*)^*$
> [name=Guest Barnes]
> I think (1+00)* is simpler and works for 17, right?

> Yes, it works as well.
> [name=Cytin7]

18. $1(11)^*(00(\varepsilon+1(11)^*))^*$
19. $((0+1)(0+1)(0+1))^*$
20. $0^*(10^*10^*10^*)^*$
21. $(000)^*(\varepsilon+011+001)(111)^*$
22. $(000)^*(001+010+100)(000)^*$
23. $(00)^*(\varepsilon+01)(11)^*(\varepsilon+10)(00)^*$
24. $00(0+1)^*11$

## 3. Direct DFA construction.
1. <img src="https://hackmd.io/_uploads/B1sVwqhas.png" style="zoom: 33%;" />
2. <img src="https://hackmd.io/_uploads/S1bXt9hpj.png" style="zoom: 50%;" />
3. <img src="https://hackmd.io/_uploads/Bk3z55nTj.png" style="zoom: 50%;" />
4. <img src="https://hackmd.io/_uploads/BJX6c52ai.png" style="zoom: 50%;" />
5. <img src="https://hackmd.io/_uploads/Hyahi52po.png" style="zoom: 50%;" />
6. <img src="https://hackmd.io/_uploads/Hkue-wppo.png" style="zoom: 55%;" />
7. <img src="https://hackmd.io/_uploads/ByXgfDa6i.png" style="zoom: 60%;" />
8. <img src="https://hackmd.io/_uploads/SyiMmDaai.png" style="zoom: 60%;" />
9. <img src="https://hackmd.io/_uploads/HyonMwppi.png" style="zoom: 60%;" />
10. <img src="https://hackmd.io/_uploads/SJdmHvpas.png" style="zoom: 60%;" />
11. <img src="https://hackmd.io/_uploads/HyWCHvTTj.png" style="zoom: 60%;" />
12. <img src="https://hackmd.io/_uploads/HJER8DT6i.png" style="zoom: 60%;" />
13. <img src="https://hackmd.io/_uploads/S1iV_P6pj.png" style="zoom: 60%;" />
14. <img src="https://hackmd.io/_uploads/HJPB3v6Ti.png" style="zoom: 60%;" />
15. <img src="https://hackmd.io/_uploads/B1a9hDpTo.png" style="zoom: 60%;" />
16. <img src="https://hackmd.io/_uploads/BJVzRv6pj.png)
" style="zoom: 60%;" />
17. <img src="https://hackmd.io/_uploads/SksSJup6j.png" style="zoom: 60%;" />
18. <img src="https://hackmd.io/_uploads/Skecb_pTj.png" style="zoom: 60%;" />
19. <img src="https://hackmd.io/_uploads/SJ6qM_T6s.png" style="zoom: 60%;" />
20. <img src="https://hackmd.io/_uploads/SJeQX_T6o.png" style="zoom: 60%;" />
21. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined as follow:
$$
\begin{align*}
Q&=\left\{0,1,2\right\}\\
\Sigma&=\left\{0,1\right\}\\
s&=0\\
A&=\left\{0\right\}\\
\delta\left(q,a\right)&=\left(2q+a\right)\ \text{mod}\ 3
\end{align*}
$$
22. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined as follow:
$$
\begin{align*}
Q&=\left\{q\mid 0\le q<5\right\}\\
\Sigma&=\left\{0,1\right\}\\
s&=0\\
A&=\left\{0\right\}\\
\delta\left(q,a\right)&=\left(7q+a\right)\ \text{mod}\ 5
\end{align*}
$$
23. <img src="https://hackmd.io/_uploads/HJAbhOp6j.png" style="zoom: 60%;" />
24. <img src="https://hackmd.io/_uploads/SkpdadT6o.png" style="zoom: 60%;" />
25. <img src="https://hackmd.io/_uploads/HJRPROT6j.png" style="zoom: 60%;" />
> [name=Guest Wilkerson]
> Start state needs to be accepting, and I think the accepting states are flipped in g
26. <img src="https://hackmd.io/_uploads/rke3kFpai.png" style="zoom: 60%;" />

## 4. Fooling sets
1. Fooling set = $0^{*}$. Take $0^i, 0^j, i > j$. Distinguish string is $1^{i-1}$
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

## 5. Regular or Not?
1.
2.
3.
4. Fooling set $F=\{{0}^n{1}\}$, suffix $0^i$ for any two strings $0^i1$ and $0^j1$, $i\neq j$.
5. The language is $\varnothing$, thus it is regular.
6. Fooling set $F=\{{0}^*\}$, suffix ${1}^{k}$ for arbitrary two strings ${0}^i$ and ${0}^j$,\\where $k=\min\{i,j\}$, $i\neq j$.
7. Fooling set $F=\{{0}^*\}$, suffix ${1}^{k}$ for arbitrary two strings ${0}^i$ and ${0}^j$,\\where $k=\max\{i,j\}$, $i\neq j$.
8. The language is finite, with $\frac{375\times376}{2}$ strings. Thus it is regular since you can union sets of every string in the language together to get the language.
9. Language $L(S)=({01})^*$
10. Fooling set $F=\{{0}^*\}$, suffix $1^i$ for arbitrary two stings $0^i$ and $0^j$, $i\neq j$.
11. Language $L=\varnothing$, since $\forall w,x\in\Sigma^*$, $\varepsilon$ is a substring for both $w$ and $x$.
12. The regular expression for $L$ is ${0}^*{\#}{1}^* + {1}^*{\#}{0}^* + {({0}+{1})}^*{\#} + {\#}{({0}+{1})}^*$.
13.
14.
15.
16.
17.
18.
19.
20.

## 6. Product/Subset Constructions
For all the questions below, the answer DFA is denoted as $M=\left(Q,\Sigma,\delta,s,A\right)$, where $\Sigma=\left\{0,1\right\}$. Denote $M_a=\left(Q_a,\Sigma,\delta_a,s_a,A_a\right)$ for condition (a), $M_b=\left(Q_b,\Sigma,\delta_b,s_b,A_b\right)$ for condition (b), and $M_c=\left(Q_c,\Sigma,\delta_c,s_c,A_c\right)$ for condition &#40;c).
Also, denote $\phi\left(\left(x,y,z\right),\left\{A_a,A_b,A_c\right\}\right)$ on $\left(Q_a\times Q_b\times Q_c\right)\times\left\{A_a,A_b,A_c\right\}\to\mathbb{N}$ as the number of true statements among $x\in A_a$, $y\in A_b$, and $z\in A_c$.
$M_a$:<img src="https://hackmd.io/_uploads/HkX4hYT6i.png" style="zoom: 60%;" />
$M_b$:<img src="https://hackmd.io/_uploads/SJeQX_T6o.png" style="zoom: 60%;" />
$M_c$:<img src="https://hackmd.io/_uploads/BJbMpKapi.png" style="zoom: 60%;" />
1. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined by the following definitions:
$$
\begin{align*}
Q&=Q_a\times Q_b\times Q_c\\
s&=\left(s_a,s_b,s_c\right)\\
A&=A_a\times A_b\times A_c\\
\delta\left(\left(x,y,z\right),a\right)&=\left(\delta\left(x,a\right),\delta\left(y,a\right),\delta\left(z,a\right)\right)
\end{align*}
$$
2. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined with same definitions as 6.1, but changing $A$ with:
$$
A=\left\{\left(x,y,z\right)\mid x\in A_a \vee y\in A_b \vee z\in A_c\right\}
$$
3. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined with same definitions as 6.1, but changing $A$ with:
$$
A=\left\{\left(x,y,z\right)\mid \phi\left(\left(x,y,z\right),\left\{A_a,A_b,A_c\right\}\right)=1 \right\}
$$
4. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined with same definitions as 6.1, but changing $A$ with:
$$
A=\left\{\left(x,y,z\right)\mid \phi\left(\left(x,y,z\right),\left\{A_a,A_b,A_c\right\}\right)=2 \right\}
$$
5. The DFA $M=\left(Q,\Sigma,\delta,s,A\right)$ is defined with same definitions as 6.1, but changing $A$ with:
$$
A=\left\{\left(x,y,z\right)\mid \phi\left(\left(x,y,z\right),\left\{A_a,A_b,A_c\right\}\right)\equiv1\ \left(\text{mod}\ 2\right) \right\}
$$

## 7. NFA Construction
1. Define the NFA $N=\left(Q,\Sigma,\delta,s,A\right)$ by the following definitions:
$$
\begin{align*}
Q&=\left\{k\mid 0\le k\le374\right\}\\
\Sigma&=\left\{0,1\right\}\\
s&=0\\
A&=\left\{k\mid k\equiv1\left(\text{mod}\ 2\right)\right\}\\
\delta\left(0,0\right)&=\left\{0\right\}\\
\delta\left(0,1\right)&=\left\{0\right\}\\
\delta\left(0,\varepsilon\right)&=\left\{1\right\}\\
\delta\left(q,1\right)&=\left\{q+1\right\},\ 1\le q<374\\
\delta\left(q,0\right)&=\left\{q\right\},\ 1\le q<374\\
\end{align*}
$$
2.
3. <img src="https://hackmd.io/_uploads/HJadkopps.png" style="zoom: 60%;" />
4.
> Official answer:


## 8. Regular Language Transformations
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

## 9. Context-Free Grammars
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

## 10. True or False Questions
### Part A
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17. F
18. F

### Part B
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.

### Part C
1.
2.
3.
4.
5.
6.
7.
8.
9.
10. 10(1=)
11.
12.
13.
14.
15.
16.
17.
18.
19.

### Part D
1.
2.
3.
4.
5.
6.

### Part E
1.
2. F
3.
4.
5.
6.
7.
8.

### Part F
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

### Part G
1.
2.
3.
4.
5.
6.
7.
8.

### Part H
1.
2.
3.
4.
5.
6.
7.
8.
9.