theory of computation

Question

L={a^n|n≥0} and L is definded over 𝚺 ={a,b} find L'

 

Answer 1

See the L={a^n|n≥0} definded over 𝚺 ={a,b} is containing the strings with number of a's ({eps, a, aa, aaa....})

now complement of this language must not contain eps,a, aa... so on to which we can also infer as It must contain atleast 1 b makin the language to be {b, ab, ba, aab, abb, aba, baa, bab,bba, bbb....}
so we can write it as (a+b)* b (a+b)* OR as L= {(a+b)^n b (a+b)^m | m,n>= 0}
 

Comments

@I_M_CK what does (a+b) mean?

 

---

+ is like an or operator when we write (a+b) it means we have to select one of a or b similarly when we write (a+b)^2 it means (a+b)(a+b) or we can say  from first a+b we can generate a or b and from 2nd (a+b) we can generate a or b making language of (a+b)^2 as aa,ab,ba,bb. similarly when we write (a+b)^n it means n times we can choose a or b

Answer 2

Atleast one b with any no a's (a+b)*b(a+b)*