## 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* `
 A 3 B 4 C 5 D 6
Theory-of-Computation       Regular Languages and Finite Automata       GATE 2014 [Set-3]
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”).
 Question 2

Consider the languages L1 = ϕ and L= {a}. Which one of the following represents L1L2* ∪ L1*?

 A {є} B ϕ C a* D {є,a}
Algorithms       Regular languages and Finite automata       GATE 2013
Question 2 Explanation:
As we know, for any regular expression R,
Rϕ = ϕR = ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
There are 2 questions to complete.

Register Now