Scribd
Upload
99 views10 pages

Assignment 5-Theory of Computation

The document contains 50 questions about regular languages and grammars including finding regular expressions for given automata, converting between grammar forms like CNF and GNF, drawing PDAs for certain languages, and properties of grammars.

Uploaded by

Khushi Agarwal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
99 views10 pages

Assignment 5-Theory of Computation

The document contains 50 questions about regular languages and grammars including finding regular expressions for given automata, converting between grammar forms like CNF and GNF, drawing PDAs for certain languages, and properties of grammars.

Uploaded by

Khushi Agarwal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Assignment-5

1) What language is accepted by the following generalized


transition graph ?

2) Find the regular expression for the language accepted by the


following automata.
3) Find the regular expression for the language accepted by the
following automata.

4) Find the regular expression for the language accepted by the


following automata.

5) Find the regular expression for the language accepted by the


following automata.
6) Find the Language accepted by the given finite automata.

7) Find the language accepted by the given machine


8) The regular expression 0*(10*) is same as
a) 1*(01*)*
b) (0+1)*
c) (0*1)*0*
d) All of these

9) Which of the following regular expression is equivalent to


(a+b)*a(a+b)*b(a+b)*
a) (a+b)*ab(a+b)*
b) a(a+b)*b(a+b)*
c) (a+b)*a(a+b)*a(a+b)*
d) (a+b)*b(a+b)*a(a+b)*

10) Find the regular expression for the given DFA


11) If G = ({S},{a},S,{S → SS}), then find language L(G).
12) The Grammer S → aSb| ε generates what language ?
13) Grammar S→bS| b | Aa, A→abc is regular or not ?
14) P, Q and R are three language. If P and R are regular and if
PQ = R the Q must be regular or not ?
15) If L1 and L2 are regular language over ∑* which of the
following statements are incorrect ?
a) L1 ∩ L2 is regular
b) L1 + L2 is regular
c) L1* is regular
d) None of above
16) Consider the following language
S→aA, A→aA| bB, B→bB|c|cC, C→c|cC
Find L(G).
17) Consider the following grammar G
S→bS | aA | b
A→bA| aB , B→bB| aS| a Find L(G) generated by G.
18) Write the grammar for the regular expression a*b*.
19) Consider the following Grammar
S→ aB| bA, A→a|aS|bAA, B→ b| bS| aBB
Find L(G) generated by above Grammar.

20) If e1 and e2 are regular expression denoting the languages L1


and L2 respectively, then is (e1)(e2) is a regular expression
denoting L1.L2 ? if not then explain why ?

21) Show why G = ({a,b},{S},S ,{S→b|Sa|aS|SS}) is ambiguous.

22) Consider the production grammar S→AB| AS, A→a|aA ,


B→b. find the regular expression obtained by above grammar.

23) Draw the Derivation tree for string id * id + id considering


following grammar E→E+E, E→E*E, E→id. Is more then one
derivation tree possible for given string(if yes then draw) ?

24) Remove unit and Useless production


S→ABc | BAab| A
A→a|ab|Ba|ε
B→bb|cc|A|ε
C→cC|bC
25) Remove unit and Useless Production
S→ABc| BAab |A
A→a|ab|Ba|B|ε
B→bb| cc| A|ε
C→cC | bC
26) Remove unit and useless production
S→ aA| a| C
A→ a| bb| aA
B→ c| dd
C→cC | dC
D→BC

27) Convert the given grammer into CNF form


S→ aAB| ab | aSb
A→ BA | Ac| Add
B→ Bb

28) Convert the given grammer in GNF form


S→ aA| aBD| aSb | ab
A→ aB| aAbc | aAbD
B→ b
D→ d

29) Convert the given grammar G in CNF and GNF.


S→ 0S0|1S1|00|11

30) Convert the grammar in CNF to a grammar in GNF.


S→ bA
A→ bAA | a

31) Convert the given grammar in GNF.


S→AB
A→BS| a
B→SA| b

32) Convert the given grammar in GNF.


S→AA| a
A→SS|b

33) Draw the PDA to accept the language L ={an bn | n >= 0}.
34) Draw the PDA to accept the language L ={an b2n | n >= 0}.
35) Draw the PDA to accept the language L ={a2n bn | n >= 0}.
36) Draw the PDA to accept the language L ={am bn | n >= 0}.
37) Draw the PDA which accepts all strings containing equal
number of a’s and equal number of b’s.
38) Draw the PDA which accepts all palindrome strings
over{a,b}.
39) Draw the PDA which accepts all Hash palindrome strings
over{a,b}.
40) Draw the PDA to accept the language L ={an bm Cm+n | n,m >=
1}.
41) Give the CFG for the following language L ={an bn | n >= 0}.

42) Which language is accepted by given Grammar S→aaSbb| ab

43) Consider the grammar S→PQ| SQ| PS, P →x, Q →y. To get
string of n terminal, the number of productions to be used is?

44) Consider grammar S→AB, A→ aAA| ε, B→bBB|, eliminate


the εproduction.

45) Consider the grammar S→ bA| aB, A→bAA| aS| a, B→aBB|


bS|a. construct an equivalent grammar L’ in CNF.How many
nodes will out degree = 0 are present in the graph of L’?
46) Consider the grammar consisting of 7 production S→aA|
aBB, A→aaA|ε, B→bB|bbC, C→B. after elimination of unit,
useless and εproduction, how many production remain in the
resulting grammar?

47) Consider the grammar S→aS|aSbS|ε, find the language


accepted by this grammar.

48) G= ({a,b},{S},S, {S→b|Sa|aS|SS}) which of the following is


true ?
a) aabbaa relates to G
b) G is ambiguous
c) Regular expression corresponding to G is ba*.

49) Consider the following grammar S→AB, A→a|aS|ε, B→b|


bS|ε. Find the equivalent CFG without ε production.

50) For the given grammar what is the equivalent CFG without
useless symbols S→AB| a , A→a.

You might also like