Question

Question: Give the formal description of the machines M₁ and M₂ pictured in

Short answer

Answer:

The solution is $\left(aUb\left(\left(eUb\left(b\right)*\right)ab\right)*\right)*\left(eUb\left(\left(eUb\left(b\right)*\right)aa\right)*b\left(b\right)*\right)$

Step-by-step solution

Definition of the states diagram

Just one resultant, q₂ , exists, as well as two non-final states, q₃ and q₁ .

We can reach q₂ in two different methods.

1. If we get ' a ' at q₁

2. If we get ' a' at q₃

This same DFA simply allows strings which finish inside the letter ' a,' according to this. However, this isn't a thorough representation. When we're in state q₂ to get a 'a ,' we'll go to non-final state q₃ , & once we get another ' a,' we'll go back to q₃ (the final state). As a result, we can readily deduce that the DFA only accepts strings with an integer value of ' 's at the end.

To achieve non-final states if we encounter ' b ' at any state $\left(q1,q2,orq3\right)\left(q1,q3orq3,respectively\right)$. Which means that perhaps the DFA will pick ' a' at any point inside this string's centre, not at the end. We can assume that we can start with whatever string we choose, but the string must end with an odd number of ' a 's.

$\left(aUb\right)*a\left(aa\right)*$is the appropriate regular expression. U indicates that we can examine one or both of the characters at the same time but not together, and * indicates that the string to which it is attached (before) can be repeated 0 or more times.

The Theorem of Arden’s   

For M₂ ,

There are two final states, q₁ , 4n two non-final states, $q_{2}and{q}_3$ .

We can reach in two ways.

1. If we get ' a ' at q₁

2. If we get ' b' at q₃

We can reach q₄ in two ways.

1. If we get 'b ' at q₂

2. If we get 'b ' at q₄

When we begin, we must first understand Arden's theorem. If a condition is written as

$R=Q+RP$

It can be reduced to

$R=QP*$

In addition to the previously described states and established letters, we must specify the symbols we will use

We can only consider one of the strings at a time, not have both.

Indicates that the string to which it is attached (previously) can be repeated or more times.

The letter stands for an empty string, which signifies there are no characters in the strings.

If we only consider the incoming transfers, we get the following formulations for the four states:

$$\begin{gathered} q_1=eU{q}_{1}aU{q}_{3}b------\left(1\right) \\ {q}_2=q_{1}bU{q}_{4}a------\left(2\right) \\ {q}_3=q_{2}aU{q}_{4}a------\left(3\right) \\ {q}_4=q_{2}bU{q}_{4}b------\left(4\right) \end{gathered}$$

To Simplify the expressions

It's worth noting that now the incoming conversions are separated by U. It is because we can only employ one of these transitions at a time to get to a certain state.

Also, keep in mind that the final regular expression will be $q_{1}U{q}_4$

Applying Arden's theorem on (4), we get

$q_4=q_{2}b\left(b\right)*$ -----(5)

Substituting (5) in (3), we get

$q_3=q_{2}aU{q}_{2}b\left(b\right)*a=q_2\left(eUb\left(b\right)*\right)a$-----(6)

Substituting (6) in (2), we get

$q_2=q_{1}bU{q}_2\left(eUb\left(b\right)*\right)aa=q_{1}b\left(\left(eUb\left(b\right)*\right)aa\right)*$-----(7) (using Arden's theorem)

Substituting (7) in (5), we get

$q_4=q_{1}b\left(\left(eUb\left(b\right)*\right)aa\right)*b\left(b\right)*$ -----(8)

Thus, our expression will be of the form

$q_{1}U{q}_4=q_{1}U{q}_{1}b\left(\left(eUb\left(b\right)*\right)aa\right)*b\left(b\right)*=q_1\left(eUb\left(\left(eUb\left(b\right)*\right)aa\right)*b\left(b\right)*\right)a$ -----(9)

Substituting (6) in (1), we get

$$\begin{gathered} q_1=eU{q}_{1}aU{q}_2\left(eUb\left(b\right)*\right)ab \\ =eU{q}_{2}aU{q}_{1}b\left(\left(eUb\left(b\right)*\right)ab\right)*\left(from\left(7\right)\right) \\ =eU{q}_1\left(aUb\left(\left(eUb\left(b\right)*\right)ab\right)*\right) \\ =e\left(aUb\left(\left(eUb\left(b\right)*\right)ab\right)*\right)*\left(u\sin gArden\text{'}stheorem\right) \\ =\left(aUb\left(\left(eUb\left(b\right)*\right)ab\right)*\right)*\left(aseisemptystring\right) \end{gathered}$$

Thus, our required regular expression is

Therefore, The Expression is

$\left(aUb\left(\left(eUb\left(b\right)*\right)ab\right)*\right)*\left(eUb\left(\left(eUb\left(b\right)*\right)aa\right)*b\left(b\right)*\right)$