GATE CSE 2022 | Question: 2

Question

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

• A. $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$
• B. $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$
• C. $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$
• D. $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$

Comments

String 'bab' can be genrate by option D , but FA cannot genrate it

---

@sahil1211 bab is accepted by FA : 1->3->1->3

 

---

Shortcut for such questions is 

Given 3 states, 

Assume u start with any of the state and return back 

U will get your expression 

Only condition is u have to do this from all states present.

Answer 1

Answer : D

$\color{red}{\text{Method 1(Complete Analysis) :}}$

We have two final states, $Q,R.$

First find the regular expression for set of all strings that end up at the initial state $P$ when running the given $\textsf{NFA}.$ Let’s call this $P.$

Note that $P$ is the initial state, so, NFA execution starts at $P.$ Now, to end up on state $P$ at the end of the string, we can do any of the following, in any order, any number of times :

1. Read $’a’$, go to state $Q,$ then read any number of $b’s$, then read $b$ to come back to state $P.$ So, $1 = ab^*b$
2. Read $’b’$, go to state $R,$ then read any number of $a’s$, then read $a$ to come back to state $P.$ So, $2= ba^*a$

So, $P = (1+2)^* = [(ab^*b)+(ba^*a)]^*$ (Because we can do $1$ or $2$ in any order, any number of times)

Now, we want to find language of the given NFA $N$, whose final states are $Q,R.$

So, $RegEx(N) = Q + R $

Where $Q$ is the regular expression for set of all strings that end up at the state $Q$ when running the given $\textsf{NFA}$ and $R$ is the regular expression for set of all strings that end up at the state $R$ when running the given $\textsf{NFA}.$

$Q = P ab^*$

$R = Pba^*$

So, $RegEx(N) = Q + R = P ab^* + Pba^* = P(ab^* + ba^*)$

$RegEx(N) = [(ab^*b)+(ba^*a)]^* (ab^* + ba^*)$

Hence, Option D is Correct Answer.

$\color{blue}{\text{Method 2 (Option Elimination) :}}$

Option A :

The Strings $\text{“}a\text{”}$ and $\text{“}b\text{”}$ are accepted by the given NFA BUT these strings are Not generated by the regular expression in Option A. So Option A is wrong.

Option B :

The String $abbbbaa$ is accepted by the given NFA BUT this string is Not generated by the regular expression in Option B. So Option B is wrong.

Option C :

The Empty String is NOT accepted by the given NFA BUT this string is generated by the regular expression in Option C. So Option C is wrong.

Correct answer is D.

Comments

I think D can generate a and b.

Ignore the first part and take only the second part. Then lets take EPSILON in place of b* then it becomes a and when we take EPSILON inplace of a* it becomes b.

So it is possible for option D to be true.

---

@jd_2706 so when there is + in between we can ignore the second part because + is "or" right? ab* + ba* we take either 1st or 2nd or both right? yeah in that case "a" as well as "b" will be generated. I got confused earlier doing too much TOC in a day 😓

---

Its okay to do mistakes,bro. Even I chose B, when I encountered this question for the first time.

Answer 2

using state elimination method :

here option D matches RE:(ba*a+ab*b)*(ab*+ba*)

Comments

Nice I also was searching for the state elimination method as solved using that

---

I think this is the best method in these type of questions ( when we are not able to do option elimination.... )

---

Thanks bro!! :) much needed soln

---

Best !

Answer 3

For option A,

The String “a” is not accepted which is in the language.So it is false.

For Option B,

The String “abbbaa” is accepted by the NFA but it is not generated by the regular expression.So it is false.

For option C,

It will accepted empty string which is not in the language.So it is false.

Correct answer is D.

Comments

The String “abb” is accepted but it is not in the language.So it is false.

 

“abb” is surely in language (ab*b)*ab*

---

@Sanjay Sharma thanks sir for poining out the mistake. I have edited the answer.

---

@Sanjay Sharma sir how to solve this using the state elimination method or state elimination method will not work here?

Answer 4

using adren’s lemma

P=∈+Qb+Ra

Q=Pa+Qb*

 by adren’s thorem

if R=Q+RP

then R=QP*

so, here

Q=Pa(b*)*……………..(1)

R=Pb+Ra*

so R=Pb(a*)*…………...(2) (by adren’s theorem)

now P=∈+Qb+Ra

     P=∈+Pa(b*)*b+ Pb(a*)*a

     P=∈+P{a(b*)*b+b(a*)*a}

    P=∈[a(b*)*b+b(a*)*a]*

    P=[a(b*)*b+b(a*)*a]*………..(3)

now from Eqn(1) and Eqn(2)

RE: Q+R=Pa(b*)*+Pb(a*)*

              =P[a(b*)*+b(a*)*]

put the value of P from equ(3)

RE: Q+R=[a(b*)*b+b(a*)*a]*[a(b*)*+b(a*)*]

RE: Q+R = [ab*b+ba*a]*[ab*+ba*]

so Option D is correct

 

Comments

That's very useful. Thank you..😊😊

---

Mention not .I too faced problems that's why I wrote this to help others to learn all possible approach.

Answer 5

Solution:- 

 

Comments

In option b: ab*    string accepted

string 'ababb' not accepted here

Answer 6

D is Correct