## Regular languages and Finite automata

Question 1 |

The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________.

a*b*(ba)*a*

3 | |

4 | |

5 | |

6 |

Question 1 Explanation:

The regular expression generate all the strings of length 0 , 1 and 2

{ϵ, a, b, aa, ab, ba, bb}

Let’s check all the string of length 3.

The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}

But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).

{ϵ, a, b, aa, ab, ba, bb}

Let’s check all the string of length 3.

The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}

But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).

Question 2 |

Consider the languages L_{1} = ϕ and L_{2 }= {a}. Which one of the following represents L_{1}L_{2}* ∪ L_{1}*?

{є} | |

ϕ | |

a* | |

{є,a} |

Question 2 Explanation:

As we know, for any regular expression R,

Rϕ = ϕR = ϕ

So L

and L

So L

Rϕ = ϕR = ϕ

So L

_{1}L_{2}* = ϕand L

_{1}* = {ϕ}* = {ϵ}So L

_{1}L_{2}* ∪ L_{1}* = {ϵ}
There are 2 questions to complete.