retagged by
17,027 views
31 votes
31 votes

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

  1. $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$
  2. $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$
  3. $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$
  4. $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$
retagged by

4 Answers

Best answer
34 votes
34 votes

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.

edited by
5 votes
5 votes
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.
edited by
2 votes
2 votes

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

 

Answer:

Related questions

13 votes
13 votes
2 answers
2
Arjun asked Feb 15, 2022
6,067 views
A function $y(x)$ is defined in the interval $[0, 1]$ on the $x – $ axis as$$y(x) = \left\{\begin{matrix} 2& \text{if} & 0 \leq x < \frac{1}{3} \\ 3& \text{if}& \frac{1...
36 votes
36 votes
2 answers
3
Arjun asked Feb 15, 2022
15,464 views
Which one of the following statements is $\text{TRUE}$ for all positive functions $f(n)?$$f(n^{2}) = \theta (f(n)^{2}),$ when $f(n)$ is a polynomial$f(n^{2}) = o (f(n)^{2...