The Gateway to Computer Science Excellence
+1 vote

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 by Boss (17.5k points)
recategorized by | 72 views
L ={ (words starting with $a$ and ending with $b$) OR (words starting with $b$ and ending with $a$) }

2 Answers

+4 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$

by Boss (19.2k points)
edited by
It's really the sensible explanation.👍
+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 $

by Boss (16.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,397 answers
105,454 users