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}
Que. Given the following expression grammar:
E->E * F | F+E | F
F-> F-F | id
Which of the following is true?
A * has higher precedence than +
B - has higher precedence than *
C + and - have same precedence
D + has higher precedence than *
Que. Consider the following two statements:
S1: {(O^2n) |n>/=1} is a regu1ar language
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language
Which of the following statements is correct?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 andS2 is correct
Que. Which of the following statements in true?
A If a language is context free it can always be accepted by a deterministic
push-down automaton
B The union of two context free languages is context free
C The intersection of two context free languages is context free
D The complement of a context free language is context free
Que. Which of the following statements is false?
A An unambiguous grammar has same leftmost and rightmost derivation
B An LL(1) parser is a top-down parser
C LALR is more powerful than SLR
D An ambiguous grammar can never be LR(k) for any k
Que. Consider the following languages:
L1={w w l w (belongs) to) {a,b}*}
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w}
L3 = { 0^2i | i is an integer}
L4 = {[(O)^i]^2| i is an integer}
Which of the languages are regular?
A Only L1 and L2
B Only L2, L3, and L4
C Only L3 and L4
D Only L3
Que. Context free language are closed under
A union, intesection
B union,kleene closure
C intesection,complement
D complement,kleene closure
Que. Context free languages are
A closed under union
B closed under complementation
C closed under intersection
D all of the above
Que. Which one is equivalent (i) (00)*(e+0) (ii) (00)* (iii) 0* (iv)
0(00)*
A (i) and (ii)
B (ii) and (iii)
C (i) and (iii)
D (iii) and (iv)
Que. Type O grammer is
A (C)both and (b) above
B (C)both (a) and above
C both (a) and (b) above
D none of these
Que. Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A 8
B 14
C 15
D 48
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}
Que. Given the following expression grammar:
E->E * F | F+E | F
F-> F-F | id
Which of the following is true?
A * has higher precedence than +
B - has higher precedence than *
C + and - have same precedence
D + has higher precedence than *
Que. Consider the following two statements:
S1: {(O^2n) |n>/=1} is a regu1ar language
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language
Which of the following statements is correct?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 andS2 is correct
Que. Which of the following statements in true?
A If a language is context free it can always be accepted by a deterministic
push-down automaton
B The union of two context free languages is context free
C The intersection of two context free languages is context free
D The complement of a context free language is context free
Que. Which of the following statements is false?
A An unambiguous grammar has same leftmost and rightmost derivation
B An LL(1) parser is a top-down parser
C LALR is more powerful than SLR
D An ambiguous grammar can never be LR(k) for any k
Que. Consider the following languages:
L1={w w l w (belongs) to) {a,b}*}
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w}
L3 = { 0^2i | i is an integer}
L4 = {[(O)^i]^2| i is an integer}
Which of the languages are regular?
A Only L1 and L2
B Only L2, L3, and L4
C Only L3 and L4
D Only L3
Que. Context free language are closed under
A union, intesection
B union,kleene closure
C intesection,complement
D complement,kleene closure
Que. Context free languages are
A closed under union
B closed under complementation
C closed under intersection
D all of the above
Que. Which one is equivalent (i) (00)*(e+0) (ii) (00)* (iii) 0* (iv)
0(00)*
A (i) and (ii)
B (ii) and (iii)
C (i) and (iii)
D (iii) and (iv)
Que. Type O grammer is
A (C)both and (b) above
B (C)both (a) and above
C both (a) and (b) above
D none of these
Que. Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A 8
B 14
C 15
D 48
No comments:
Post a Comment