Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Find the regular expression for the language accepted by the automata given below.





Solution

Let the states be $q_0,q_1,q_2$.

Here, $q_0$ is start state and final state.

From the diagram:

$q_0\xrightarrow{a}q_1$

$q_1\xrightarrow{b}q_0$

$q_1\xrightarrow{a}q_2$

$q_2\xrightarrow{b}q_1$

$q_0\xrightarrow{b}q_2$

Now, paths from $q_0$ back to $q_0$ are:

$q_0\xrightarrow{a}q_1\xrightarrow{b}q_0$, giving $ab$

Also,

$q_0\xrightarrow{b}q_2\xrightarrow{b}q_1\xrightarrow{b}q_0$, giving $bbb$

In general, from $q_1$ to $q_0$ we can have:

$(ab)^*b$

So, complete cycle from $q_0$ to $q_0$ is:

$(a+bb)(ab)^*b$

Since $q_0$ is final, these cycles can repeat any number of times.

Required regular expression is:

$((a+bb)(ab)^*b)^*$


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...