Compiler-As-1

Question 1

Let $\mathrm{\Sigma }=\{a,b\}.$Design a DFA for each following language (6 marks for each)

$a.L_1=\{a{b}^{n}a|n\ge 2\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_5$
$q_1$	$q_5$	$q_2$
$q_2$	$q_5$	$q_3$
$q_3$	$q_4$	$q_3$
$q_4$	$q_5$	$q_5$
$q_5$	$q_5$	$q_5$

$b.L_2=\{b{a}^n|n\ge 1andn\ne 3\}$

Current State	$a$	$b$
$q_0$	$q_6$	$q_1$
$q_1$	$q_2$	$q_6$
$q_2$	$q_3$	$q_6$
$q_3$	$q_4$	$q_6$
$q_4$	$q_5$	$q_6$
$q_5$	$q_5$	$q_6$
$q_6$	$q_6$	$q_6$

$c.L_3=\{w||w|mod3\ne 0\},where|w|isthelengthofthestringw.$

Current State	$a$	$b$
$q_0$	$q_1$	$q_1$
$q_1$	$q_2$	$q_2$
$q_2$	$q_0$	$q_0$

Question 2

Design a regular expression for each language in Q1. (6 marks for each)

a. $abb{b}^{\ast }a$ b. $b(a|aa|aaaa{a}^{\ast })$ c. $((a|b)(a|b)(a|b){)}^{\ast }((a|b)|((a|b)(a|b)))$

Question 3

Let $\mathrm{\Sigma }=\{0,1\}.$ Convert the regular expression $(00{)}^{\ast }|(1(0|1{)}^{\ast })$ to an NFA. (10 marks)

Question 4

Given the following NFA

a. Convert the NFA to the equivalent DFA. (20 marks)

First iteration

• $U_0=ϵ-closure(Q_1)=\{Q_1,Q_2,Q_5\}$
• $move(U_0,0)=\{Q_3,Q_5\}$
• $ϵ-closure(move(U_0,0))=\{Q_3,Q_5\}=U_1$
• $move(U_0,1)=\{Q_3,Q_5,Q_6\}$
• $ϵ-closure(move(U_0,1))=\{Q_3,Q_5,Q_6\}=U_2$

Second iteration

• $move(U_1,0)=\{Q_4\}$
• $ϵ-closure(move(U_1,0))=\{Q_2,Q_4,Q_5\}=U_3$
• $move(U_1,1)=\{Q_4,Q_5,Q_6\}$
• $ϵ-closure(move(U_1,1))=\{Q_2,Q_4,Q_5,Q_6\}=U_4$

Third iteration

• $move(U_2,0)=\{Q_4,Q_5,Q_7\}$
• $ϵ-closure(move(U_2,0))=\{Q_2,Q_4,Q_5,Q_7\}=U_5$
• $move(U_2,1)=\{Q_4,Q_5,Q_6\}$
• $ϵ-closure(move(U_2,1))=\{Q_2,Q_{4,}{Q}_5,Q_6\}=U_4$

Fourth iteration

• $move(U_3,0)=\{Q_3,Q_5\}$
• $ϵ-closure(move(U_3,0))=\{Q_3,Q_5\}=U_1$
• $move(U_3,1)=\{Q_3,Q_5,Q_6\}$
• $ϵ-closure(move(U_3,1))=U_2$

Fifth iteration

• $move(U_4,0)=\{Q_3,Q_5,Q_7\}$
• $ϵ-closure(move(U_4,0))=\{Q_3,Q_5,Q_7\}=U_6$
• $move(U_4,1)=\{Q_3,Q_5,Q_6\}$
• $ϵ-closure(move(U_4,1))=U_2$

Sixth iteration

• $move(U_5,0)=\{Q_3,Q_5\}$
• $ϵ-closure(move(U_5,0))=U_1$
• $move(U_5,1)=\{Q_3,Q_5,Q_6\}$
• $ϵ-closure(move(U_5,1))=U_2$

Seventh iteration

• $move(U_6,0)=\{Q_4,Q_5\}$
• $ϵ-closure(move(U_5,0))=\{Q_2,Q_4,Q_5\}=U_3$
• $move(U_6,1)=\{Q_4,Q_5,Q_6\}$
• $ϵ-closure(move(U_5,1))=\{Q_2,Q_4,Q_5,Q_6\}=U_4$

$Q$	$Q^{{}^{\prime }}$	$0$	$1$
$\{Q_1,Q_2,Q_5\}$	$U_0$	$U_1$	$U_2$
$\{Q_3,Q_5\}$	$U_1$	$U_3$	$U_4$
$\{Q_3,Q_5,Q_6\}$	$U_2$	$U_5$	$U_4$
$\{Q_2,Q_4,Q_5\}$	$U_3$	$U_1$	$U_2$
$\{Q_2,Q_4,Q_5,Q_6\}$	$U_4$	$U_6$	$U_2$
$\{Q_2,Q_4,Q_5,Q_7\}$	$U_5$	$U_1$	$U_2$
$\{Q_3,Q_5,Q_7\}$	$U_6$	$U_3$	$U_4$

b. Minimize the DFA in part a). (20 marks)

Initially, $Q=\{\{U_1,U_2,U_5,U_6\},\{U_0,U_3,U_4\}\}$

• $\delta (U_1,0)=U_3,\delta (U_1,1)=U_4$
• $\delta (U_2,0)=U_5,\delta (U_2,1)=U_4$
• $\delta (U_5,0)=U_1,\delta (U_5,1)=U_2$
• $\delta (U_6,0)=U_3,\delta (U_6,1)=U_4$

$U_1$ and $U_6$ act in the same way, Thus $U_1$ and $U_6$ should be in the same group.

$L_1=\{U_1,U_6\}$ $L_2=\{U_2\}$ $L_3=\{U_5\}$

$Q$	$Q^{{}^{\prime }}$	$0$	$1$
$\{Q_1,Q_2,Q_5\}$	$U_0$	$U_1$	$U_2$
$\{Q_3,Q_5\}$	$U_1$	$U_3$	$U_4$
$\{Q_3,Q_5,Q_6\}$	$U_2$	$U_5$	$U_4$
$\{Q_2,Q_4,Q_5\}$	$U_3$	$U_1$	$U_2$
$\{Q_2,Q_4,Q_5,Q_6\}$	$U_4$	$U_1$	$U_2$
$\{Q_2,Q_4,Q_5,Q_7\}$	$U_5$	$U_1$	$U_2$

• $\delta (U_0,0)=U_1,\delta (U_0,1)=U_2$
• $\delta (U_3,0)=U_1,\delta (U_3,1)=U_2$
• $\delta (U_4,0)=U_1,\delta (U_4,1)=U_2$

$L_4=\{U_0,U_3,U_4\}$

$U_0$ and $U_3$ act in the same way, Thus $U_0$ and $U_3$ should be in the same group.

$Q$	$Q^{{}^{\prime }}$	$0$	$1$
$\{Q_1,Q_2,Q_5\}$	$U_0$	$U_1$	$U_2$
$\{Q_3,Q_5\}$	$U_1$	$U_0$	$U_0$
$\{Q_3,Q_5,Q_6\}$	$U_2$	$U_5$	$U_0$
$\{Q_2,Q_4,Q_5,Q_7\}$	$U_5$	$U_1$	$U_2$

Finally, the minimized DFA is:

$L_1=\{U_1,U_6\}$$L_2=\{U_2\}$$L_3=\{U_5\}$$L_4=\{U_0,U_3,U_4\}$

Question 5

Consider a new alphabet $\mathrm{\Sigma }=\{a,\dots ,z\}$

a. Design a DFA with a trap state which recognizes the keywords if or else. (The DFA does not accept any other string.) (10 marks)

b. Represent the DFA using a transition table. (4 marks)

$\delta$	$i$	$f$	$e$	$l$	$s$	$other$
$u_0$	$U_1$	$U_2$	$U_3$	$U_2$	$U_2$	$U_2$
$u_1$	$U_2$	$U_4$	$U_2$	$U_2$	$U_2$	$U_2$
$u_2$	$U_2$	$U_2$	$U_2$	$U_2$	$U_2$	$U_2$
$u_3$	$U_2$	$U_2$	$U_2$	$U_5$	$U_2$	$U_2$
$u_4$	$U_2$	$U_2$	$U_2$	$U_2$	$U_2$	$U_2$
$u_5$	$U_2$	$U_2$	$U_2$	$U_2$	$U_6$	$U_2$
$u_6$	$U_2$	$U_2$	$U_7$	$U_2$	$U_2$	$U_2$
$u_7$	$U_2$	$U_2$	$U_2$	$U_2$	$U_2$	$U_2$