CS $3350$

Homework $2,\frac{1}{31}\frac{?}{24}$

Spring $2024$

Consider the DFA defined by the state diagram below. Follow the algorithm seen in class and in our textbook to find the regular expression accepted by this DFA. The alphabet is $=\{a,b\}$

numework $2,\frac{1}{01}\frac{?}{24}$

opring ZOVZ$4$

$2.$ Let us eliminate the node $q_1.$ Let us create the "label of the new arrows" $($new Regular expression$)$ step by step

$($a$)$ Can we go from $S$ to $q_2^{}$ directly?, if yes, write the regular expression

$R_{s2}=$

Otherwise, write $\frac{O}{?}.$

$($b$)$ How can we go from $S$ to $q_2$ through $q_1($the one we are eliminating$)?$ write: The regular expression from $S$ to $q_1(R_{s1}),$ then write the regular expression from $R1$ to itself $($loops$),$ as many times as you desire $(R_{11}^{**}),$ and finally write the regular expression from $q_1$ to $q_2(R_{12}).$

The new regular expression $R_{s2}$ will be

$R_{s2}=R_{s2}{R}_{s1}{R}_{11}^{**}{R}_{12}=$

Repeat the process:

$R_{s3}=R_{s3}{R}_{s1}{R}_{11}^{**}{R}_{13}=$

$R_{sa}=R_{sa}{R}_{s1}{R}_{11}^{**}{R}_{1a}=$

$R_{22}=R_{22}{R}_{21}{R}_{11}^{**}{R}_{12}=$

$R_{23}=R_{23}{R}_{21}{R}_{11}^{**}{R}_{13}=$

$R_{2a}=R_{2a}{R}_{21}{R}_{11}^{**}{R}_{1a}=$

$R_{32}=R_{32}{R}_{31}{R}_{11}^{**}{R}_{12}=$

$R_{33}=R_{33}{R}_{31}{R}_{11}^{**}{R}_{13}=$

$R_{3a}=R_{3a}{R}_{31}{R}_{11}^{**}{R}_{1a}=$

You have a NSF with four $(4)$ states, and you have the regular expression from each state to another. Please, draw the NSF with four states and label the arrows: