search
Log In
0 votes
197 views

Consider this regular expression:  r = (a*b)* + (b*a)*


This is equivalent to


(a) (a + b)*

(b) (a + b)* · (ab)+ + (a + b)* (ba)+


(c) (a + b)*a + (a + b)* b

(d) None of above

in Theory of Computation
edited by
197 views
1
a should be answer ...as eplison is generated by r and a ..and other strings too ..
0
but how aaba string is generated from  r
0
from (b* a)* ===> take 3 times

1) a by taking b* = ∈

2) a by taking b* = ∈

3) ba by taking b* = b
0
tq
1
i think option (d) is correct .ababa is not in the language but can be generated by option (a) so none of these is coorect option.
0

hi .. look at this :

in option B) just consider second part ...that is   (a + b)* (ba)+

now (a+b)^3(ba)+ gives us =(a+b)(a+b)(a+b)(ba) now i have option that from first 3 brackest i can take a or b as per my wish ..so 

take a form 1st b from second and a agian from 3rd so we get (ababa)...so string generated, similarily you can take First part of C option and cross check that same string can also be genertaed by option C.

 

0
is ababa is in original language??????can you generate it  from original language???
0
Yes you can generate ababa from given language
0
how?????
0

take second part of r

that is ((b*a)*

now take b* as episolon = (b^0 .a)(b^1a)(b^1a)...generated form it.

0
oh its my mistake.but option(a) is not correct.
0
a is correct bro ...it generates strings with alpahabets a and b with Epsilon too ..

while b and c also generate same except that they failed to generate epsilon.

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
93 views
Let A be a regular set. Consider the two sets below L1={x | $\exists n\geq 0, \exists y\epsilon A :$ y=$x^n$} L2={x | $\exists n\geq 0, \exists y\epsilon A :$ x=$y^n$} which of the following statements is true? L1 and L2 both are regular L1 is regular but L2 is not L1 is not regular but L2 is L1 and L2 both are non-regular
asked Mar 17, 2019 in Theory of Computation aditi19 93 views
2 votes
1 answer
2
388 views
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
asked Apr 30, 2019 in Theory of Computation srestha 388 views
0 votes
1 answer
3
307 views
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________ Answer will be $3$ or $6?$
asked Apr 23, 2019 in Theory of Computation srestha 307 views
0 votes
3 answers
4
2k views
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ ... Recursive $(B)$ Non-Recursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
asked Apr 13, 2019 in Theory of Computation srestha 2k views
...