Question

For the following regular expressions, draw the FA (Finite Automata) recognizing the corresponding language. [5]

i) $ab^* + ba^* + b^*a + (a^*b)^*$ ii) $b^*a (a+b)^*ab^*$

Answer 1

FA drawings as above

Answer 2

To draw the Finite Automata (FA) for the given regular expressions, we will construct Non-deterministic Finite Automata (NFA) using standard conversion rules.

Part i) $ab^* + ba^* + b^*a + (a^*b)^*$

This regular expression is a union of four sub-expressions. We will construct an NFA for each sub-expression and then combine them using a new start state and a new final state connected by $\epsilon$-transitions.

Let $Q_{start}$ be the global initial state and $Q_{final}$ be the global final state.

1. FA for $ab^*$:

   • State $Q_{1,1}$ (initial for this component) transitions to $Q_{1,2}$ on 'a'.
   • State $Q_{1,2}$ has a self-loop on 'b'.
   • $Q_{1,2}$ is the final state for this component.
   • Transitions: $Q_{start} \xrightarrow{\epsilon} Q_{1,1}$, $Q_{1,1} \xrightarrow{a} Q_{1,2}$, $Q_{1,2} \xrightarrow{b} Q_{1,2}$, $Q_{1,2} \xrightarrow{\epsilon} Q_{final}$.

2. FA for $ba^*$:

   • State $Q_{2,1}$ (initial for this component) transitions to $Q_{2,2}$ on 'b'.
   • State $Q_{2,2}$ has a self-loop on 'a'.
   • $Q_{2,2}$ is the final state for this component.
   • Transitions: $Q_{start} \xrightarrow{\epsilon} Q_{2,1}$, $Q_{2,1} \xrightarrow{b} Q_{2,2}$, $Q_{2,2} \xrightarrow{a} Q_{2,2}$, $Q_{2,2} \xrightarrow{\epsilon} Q_{final}$.

3. FA for $b^*a$:

   • State $Q_{3,1}$ (initial for this component) has a self-loop on 'b'.
   • State $Q_{3,1}$ transitions to $Q_{3,2}$ on 'a'.
   • $Q_{3,2}$ is the final state for this component.
   • Transitions: $Q_{start} \xrightarrow{\epsilon} Q_{3,1}$, $Q_{3,1} \xrightarrow{b} Q_{3,1}$, $Q_{3,1} \xrightarrow{a} Q_{3,2}$, $Q_{3,2} \xrightarrow{\epsilon} Q_{final}$.

4. FA for $(a^*b)^*$:

   • Let's first construct FA for $a^*b$:
     • State $Q_{4,2}$ has a self-loop on 'a'.
     • From $Q_{4,2}$, it transitions to $Q_{4,3}$ on 'b'.
     • $Q_{4,2}$ is the start of $a^*b$, $Q_{4,3}$ is the end of $a^*b$.
   • Now apply Kleene star:
     • State $Q_{4,1}$ is the initial state for $(a^*b)^*$.
     • $Q_{4,1}$ transitions to $Q_{4,2}$ via $\epsilon$ (start of $a^*b$).
     • $Q_{4,1}$ transitions to $Q_{final}$ via $\epsilon$ (for the empty string, i.e., zero repetitions of $a^*b$).
     • $Q_{4,3}$ transitions back to $Q_{4,1}$ via $\epsilon$ (for repetitions of $a^*b$).
     • $Q_{4,3}$ transitions to $Q_{final}$ via $\epsilon$ (end of $a^*b$ to global final).
   • Transitions: $Q_{start} \xrightarrow{\epsilon} Q_{4,1}$, $Q_{4,1} \xrightarrow{\epsilon} Q_{final}$, $Q_{4,1} \xrightarrow{\epsilon} Q_{4,2}$, $Q_{4,2} \xrightarrow{a} Q_{4,2}$, $Q_{4,2} \xrightarrow{b} Q_{4,3}$, $Q_{4,3} \xrightarrow{\epsilon} Q_{4,1}$, $Q_{4,3} \xrightarrow{\epsilon} Q_{final}$.

The complete NFA is shown below:

Part ii) $b^*a (a+b)^*ab^*$

This regular expression is a concatenation of five parts. We will construct an NFA for each part and then concatenate them sequentially.

Let $Q_0$ be the initial state and $Q_F$ be the final state.

1. FA for $b^*$:

   • State $Q_0$ (initial) has a self-loop on 'b'. $Q_0$ is also a final state for this part.
   • Transitions: $Q_0 \xrightarrow{b} Q_0$.

2. FA for $a$:

   • State $Q_1$ transitions to $Q_2$ on 'a'. $Q_2$ is a final state for this part.
   • Transitions: $Q_1 \xrightarrow{a} Q_2$.

3. FA for $(a+b)^*$:

   • State $Q_3$ has self-loops on 'a' and 'b'. $Q_3$ is also a final state for this part.
   • Transitions: $Q_3 \xrightarrow{a} Q_3$, $Q_3 \xrightarrow{b} Q_3$.

4. FA for $a$:

   • State $Q_4$ transitions to $Q_5$ on 'a'. $Q_5$ is a final state for this part.
   • Transitions: $Q_4 \xrightarrow{a} Q_5$.

5. FA for $b^*$:

   • State $Q_6$ has a self-loop on 'b'. $Q_6$ is also a final state for this part.
   • Transitions: $Q_6 \xrightarrow{b} Q_6$.

Now, concatenate these components using $\epsilon$-transitions. The final state of one component becomes the initial state of the next via an $\epsilon$-transition. The first component's initial state is the overall initial state, and the last component's final state is the overall final state.

• $Q_0$ is the overall initial state.
• The final states of $b^*$ are $Q_0$.
• Connect $Q_0$ to $Q_1$ (start of 'a') via $\epsilon$.
• The final states of 'a' are $Q_2$.
• Connect $Q_2$ to $Q_3$ (start of $(a+b)^*$) via $\epsilon$.
• The final states of $(a+b)^*$ are $Q_3$.
• Connect $Q_3$ to $Q_4$ (start of 'a') via $\epsilon$.
• The final states of 'a' are $Q_5$.
• Connect $Q_5$ to $Q_6$ (start of $b^*$) via $\epsilon$.
• The final states of $b^*$ are $Q_6$.
• $Q_6$ is the overall final state.

The complete NFA is shown below:

The final state $Q_6$ can also be the final state directly. The $\epsilon$ transition from $Q_6$ to $Q_{final}$ is optional if $Q_6$ is marked as final.

The solution involves constructing Non-deterministic Finite Automata (NFA) for the given regular expressions. For regular expressions involving union ($+$), a new start state and a new final state are introduced, with $\epsilon$-transitions connecting the new start state to the start states of the individual components and the final states of the individual components to the new final state. For concatenation, $\epsilon$-transitions are used to connect the final state of one component's FA to the initial state of the next component's FA. For Kleene star ($*$), the standard construction involves creating a loop using $\epsilon$-transitions from the final state back to the initial state of the sub-expression, and also an $\epsilon$-transition from the initial state to the final state to account for zero repetitions.