search
Log In
2 votes
433 views

Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$?

  1. $aba$
  2. $bab$
  3. $abba$
  4. $aabb$
in Theory of Computation
recategorized by
433 views
1
L ={ (words starting with $a$ and ending with $b$) OR (words starting with $b$ and ending with $a$) }
0
option D..

3 Answers

5 votes

Answer: $\mathbf{(D)}$

As the above Regular expression is the $\mathbf{UNION}$ Of two Regular Expressions in which the first one starts with a and ends with b followed by any number of a and b in between.

In the second part, it must start with b and ends with a, followed by any number of a and b in between.

On checking the options we can easily eliminate a, b and c as they both start and end with the same symbol.

$\therefore$ The answer is $\mathbf D$


edited by
1
It's really the sensible explanation.πŸ‘
1
Thanks.
2 votes

Only Option D) can be generated

Given $r= a(a+b)^{*}b + b(a+b)^{*}a$

$a(a+b)(a+b)b = aabb $

0 votes
optino D is the correct.This R.E. represent the string which start a or end with B and vice-versa

Related questions

1 vote
2 answers
1
224 views
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend. If Deepa does not attend, which of the following is true? Chetan does not attend Akash does not attend either (A) or (B) none of the above
asked Sep 13, 2019 in Quantitative Aptitude gatecse 224 views
1 vote
1 answer
2
115 views
In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional information that can determine the winner? Geetha finishes ahead of Divya and Vani finishes ahead of Shalini. Aparna finishes ahead of Shalini. Divya finishes ahead of Geetha. None of the above.
asked Sep 13, 2019 in Quantitative Aptitude gatecse 115 views
5 votes
2 answers
3
219 views
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$
asked Sep 13, 2019 in Graph Theory gatecse 219 views
1 vote
1 answer
4
132 views
How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$ $\binom{2m}{n}$ $\binom{m}{n}$ $\binom{m+n}{n}$ $m^{n}$
asked Sep 13, 2019 in Combinatory gatecse 132 views
...