MadeEasy Subject Test: Theory of Computation - Regular Expressions

Question

sometimes questions like this will take more time plz anyone provide shortcut to this type ,this is easy but many time checking from 0 length to onward is very time consuming. 

length of the shortest string not in the language over the alphabet${a,b}$ of following regular expression is............

$a^{*}(a+ba)^{*}b^{*}$

Answer 1

Regular Expression-$a^{*}(a+ba)^{*}b^{*}$

0 length string-$\epsilon{\color{Green} \checkmark}$

1 Length string-

$a\ \ \ accepted{\color{Green} \checkmark}$

$b\ \ \ accepted{\color{Green} \checkmark}$

2 length string-

$aa\ \ \ accepted{\color{Green} \checkmark}$

$ab\ \ \ accepted{\color{Green} \checkmark}$

$ba\ \ \ accepted{\color{Green} \checkmark}$

$bb\ \ \ accepted{\color{Green} \checkmark}$

3 length string-

$aaa\ \ \ accepted{\color{Green} \checkmark}$

$aab\ \ \ accepted{\color{Green} \checkmark}$

$aba\ \ \ accepted{\color{Green} \checkmark}$

$baa\ \ \ accepted{\color{Green} \checkmark}$

$bab\ \ \ accepted{\color{Green} \checkmark}$

$bba\ \ \ not \ accepted{\color{Red} \times}$

$abb\ \ \ accepted{\color{Green} \checkmark}$

$bbb\ \ \ accepted{\color{Green} \checkmark}$

Here we can see 3 length string $bba$ can't be accepted by given regular expression.

 

Hence, length of the shortest string not in the language over the alphabet${a,b}$ of the regular expression $a^{*}(a+ba)^{*}b^{*}$ is 3.

Comments

sir i asked only that there is any shortcut

---

There should be no problem for checking 1 and 2 length string.we can see clearly all are accepted.Now, look at the R.E.

here you can generate the string like {b,bb,bbb....}and {ba, baba,baba} but you can't generate string like {bba,bbba,bbbba}.

It's about practice. it's not time time-consuming question.It will take max to max 1 min.

---

okiiii.. thank u sir