Theory of Automata

Q. Write a r.e to denote a language L which accepts all the strings which begin or end with either 00 or 11.

Ans:
The r.e consists of two parts:
L1=(00+11) (any no of 0’s and 1’s)
=(00+11)(0+1)*
L2=(any no of 0’s and 1’s)(00+11)
=(0+1)*(00+11)
Hence r.e R=L1+L2
=[(00+11)(0+1)*] + [(0+1)* (00+11)]

Q.Construct a r.e for the language which accepts all strings with atleast two c’s over
the set ={c,b}

Ans:
(b+c)* c (b+c)* c (b+c)*

Q.Construct a r.e for the language over the set ={a,b} in which total number of
a’s are divisible by 3

Ans:
( b* a b* a b* a b*)*

Q.what is:
(i) (0+1)*
(ii)(01)*
(iii)(0+1)
(iv)(0+1)+

Ans:
(0+1)*= { , 0 , 1 , 01 , 10 ,001 ,101 ,101001,…………………}
Any combinations of 0’s and 1’s.

(01)*={ , 01 ,0101 ,010101 ,…………………………………..}
All combinations with the pattern 01.

(0+1)= 0 or 1,No other possibilities.

(0+1)+= {0,1,01,10,1000,0101,………………………………….}

Q.Reg exp denoting a language over ={1} having
(i)even length of string (ii)odd length of a string
Ans:
(i) Even length of string R=(11)*
(ii) Odd length of the string R=1(11)*

Q.Reg exp for:
(i)All strings over {0,1} with the substring ‘0101’
(ii)All strings beginning with ’11 ‘ and ending with ‘ab’
(iii)Set of all strings over {a,b}with 3 consecutive b’s.
(iv)Set of all strings that end with ‘1’and has no substring ‘00’

Ans:
(i)(0+1)* 0101(0+1)*
(ii)11(1+a+b)* ab
(iii)(a+b)* bbb (a+b)*
(iv)(1+01)* (10+11)* 1

Q. Reg exp for the language such that every string will have atleast one ‘a’ followed
by atleast one ‘b’.

Ans: R=a+b+

Q. What are the applications of pumping lemma?
Ans:
Pumping lemma is used to check if a language is regular or not.
(i) Assume that the language(L) is regular.
(ii) Select a constant ‘n’.
(iii) Select a string(z) in L, such that |z|>n.
(iv) Split the word z into u,v and w such that |uv|<=n and |v|>=1.
(v) You achieve a contradiction to pumping lemma that there exists an ‘i’
Such that uviw is not in L.Then L is not a regular language.

Q. Find the grammar for the language L={a2n bc ,where n>1 }

Ans:
let G=( {S,A,B}, {a,b,c} ,P , {S} ) where P:
S->Abc
A->aaA |

Q. 16.Find the language generated by :
S->0S1 | 0A | 0 |1B | 1
A->0A | 0 , B->1B | 1

Ans:
The minimum string is S-> 0 | 1
S->0S1=>001
S->0S1=>011
S->0S1=>00S11=>000S111=>0000A111=>00000111
Thus L={ 0n 1 m | m not equal to n, and n,m >=1}

Q.Construct the grammar for the language L={ an b an | n>=1}.

Ans: The grammar has the production P as:
S->aAa
A->aAa | b
The grammar is thus : G=( {S,A} ,{a,b} ,P,S)

Q. Construct a grammar for the language L which has all the strings which are all
palindrome over ={a, b}.

Ans:
G=({S}, {a,b} , P, S )
P:{ S -> aSa ,
S-> b S b,
S-> a,
S->b,
S-> } which is in palindrome.

Q. Let G= ( {S,C} ,{a,b},P,S) where P consists of S->aCa , C->aCa |b. Find L(G).

Ans:
S-> aCa => aba
S->aCa=> a aCa a=>aabaa
S->aCa=> a aCa a=> a a aCa a a =>aaabaaa
Thus L(G)= { anban ,where n>=1 }

Q. Find L(G) where G= ( {S} ,{0,1}, {S->0S1 ,S-> },S )

Ans :
S-> , is in L(G)
S-> 0S1 =>0 1=>01
S->0S1=>0 0S11=>0011
Thus L(G)= { 0n1n | n>=0}