PESIT SOUTHCAMPUS QUESTION BANK Faculty: Mr. Karthik S
Total Hours: 52
Chapter 1 & 2 : Introduction to theory of computation and finite automata
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
24 25 26 27
28 29
Define language accepted by DFA Define a regular language Give the formal definition of NFA Define extended transition function for NFA Define language accepted by a NFA Define dead configuration in case of NFA What are the advantages of non-deterministic FA Give the formal definition of NFA Define the terms prefix and suffix of a string, productions, Sententential form. Compare NFA & DFA Define the terms alphabet, string ,prefix, suffix, language give examples to each. Define an automata for serial binary adder Define acceptors & transducers. Write a note on applications of formal languages and automata. Explain the operation of a Deterministic Finite Acceptor (DFA) with a diagram. Distinguish between NFA & DFA. Define the equivalence between two finite acceptors ? Define distinguishable and indistinguishable states. Derive the DFA that accepts the language L = { anb : n >= 0 } Find the DFA that recognizes the set of all string on Σ={a,b} starting with the prefix “ab” Find the DFA that accepts all strings on alphabet {0,1} except those containing substring 001. Give the procedure to reduce number of states in DFA. Give Nondeterministic finite Automata accepting the following Language The set of strings in (0+1)* such that some two 0’s are separated by a string whose length is 4i, for some i >=0. Give a description about FA with empty moves Construct DFA for the set of all strings beginning with a 1 which interpreted as the binary representation of an integer, is congruent to zero modulo 5 Construct DFA accepting the following language The set of all strings such that the 10th symbol from the right end is 1. Explain different units of automata. Explain the terms 1) Configuration 2) Move 3) Transition functions Show that the language L = { awa : w ∈ {a,b}* } is regular ? Also show that L2 is regular? Construct a DFA & NFA to accept all string in {a,b} such that every “a” has one “b” immediately to its right ? Define: a) Symbol or element b) Alphabet(Σ) c) String(w,u,v) d) Concatenation of strings e) Reverse of string f) length of string g) substring, prefix, suffix of a string g) wn h) Σ* i) Σ+
PESIT-BSC Education For The Real World
2 2 2 2 2 2 2 2* 4* 4* 5* 5* 5 5 5 5 5 5 5* 5* 5* 5* 5
5 5 5 8
8 8
PESIT SOUTHCAMPUS 30 31
32 33
34 35
36 37
Define the language accepted by DFA, when is the language called regular. Show that the language L= {awa :w∈{a,b}*} is regular. Draw NFA for transition table given below: States Input A B Q0 {q2} {q0,q1} Q1 Q0 {q1} Q2 {q0,q1}
Define a) Language (L) b) Sentence c) Complement(L’) d) LR e) L1.L2 f) Ln g) L* h) L Give the formal definition of DFA ? Explain transition graph ? Give an example ? Define extended transition function ( δ* ) ? Define transition table ? Draw the transition table, transition diagram , transition function of DFA a) which accepts strings which have odd number of a’s and b’s over the alphabet {a,b} b) which accepts string which have even number of a’s and b’s over the alphabet {a,b} c) which accepts all strings ending in 00 over alphabet {0,1} d) which accepts all strings having 3 consecutive zeros e) which accepts all strings having 5 consecutive ones f) which accepts all strings having even number of symbols? Give DFA & NFA which accept the language { (10)n : n ≥ 0 } Prove the equivalence between DFA & NFA OR Let L be the language accepted by a NFA MN = ( QN,Σ,δN,QN ,FN). Then prove that there exists a deterministic finite acceptor MD = ( QD,Σ,δD,QD ,FD) such that L = L(MD). Define grammar, proof techniques, language. Convert the following NFA to DFA
b
q0
a
q1
λ
q2
a
ii) 0
q0
1
0,1
q1
0,1
q2
PESIT-BSC Education For The Real World
8* 8*
10 10
10 10
7* 10*
PESIT SOUTHCAMPUS
1) Reduce the number of states in DFA 0,1
1 q1
q3
0
Q0
0 1
q2
1
q4
q5 0,1
0
1
0
Chapter 3 & 4 : Regular Expressions and languages, Properties of Regular Languages.
1 2 3 4 5 6 7 8 9 10 11 12
13 14 15
16
Give the formal definition of a regular expression with example. Define a linear grammar. Define unit production. Define regular grammar with example. How is language L( R ) denoted by regular expression “R” defined ? Give examples. Find all strings in L ((a+b)*b(a+ab)*) of length less than four Show that the automaton generated by procedure reduce is deterministic Write the NFA which accepts L( r ) where r = ( a + bb)*(ba* + λ ) Prove that “ Language generated by a right linear grammar is a regular language” Define regular expression ,Give a regular expression for L={anbm : n ≥ 4, m≤3} Show that family of regular languages are closed under intersection. Define homomorphism and homomorphic image. Let ∑ ={a,b} and ={a,b,c} and h is defined by h(a) =ab ,h(b) =bbc,if w=aba what is h(w)? and if L={aa,aba}, what is h(L)? Define Regular expression and language denoted by any regular expression Find Regular expression for the language L ={w∈{0,1}* : w has no pairs of Consecutive zeros. Prove the following identities for regular expression r,s and t here r=s means L(r)=L(s) r+s=s+r, (rs)t=r(st),(r+s)t=rt+st Prove or disprove the following for regular expressions r,s,and t
PESIT-BSC Education For The Real World
2 2 2 2 5 5* 5* 5* 5* 5* 5* 5*
4* 6* 6
6
PESIT SOUTHCAMPUS 17 18 19 20 21 22 23
24 25
26 27 28 29 30 31 32 33 34 35 36
37
38
(rs+r)r=r(sr+r)* Prove that class of Regular sets is closed under quotient with arbitrary sets Prove that the class of regular sets is closed under Substitution Prove that The class of Regular sets is closed under homomorphism and inverse homomorphism Find the NFA that accepts the language L{ab*aa+bba*ab) Construct right and left linear grammar for the language L ={an bm :n≥ 2 ,m ≥ 3 Let L1= L(a*baa*) and L2= L(aba*) find L1/L2 Give the set notation of language L( R ) denoted by regular expressions given below. a) a* . ( a + b ) b) (a+b) * (a+bb) c) (aa)* (bb)* b Prove the following: If the states qa and qb are indistinguishable, and if qc and qa n n ar distinguishable, then qb,qc must be indistinguishable. Let r be a regular expression. Then prove that there is some NFA that accepts L( r ) & hence L( r ) is a regular language. Let L be a regular language i.e., there is a NFA that accepts L. Then prove that there exists a regular expression “r” such that L = L( R ) Explain generalized transition graphs & how they are used for writing regular expression denoting same language as given NFA. Construct the finite automaton that accepts the language generated by grammar ( { V0 ,V1 } , {a,b} , {V0} , { V0 → aV1 , V1 → abV0|b } ) P.T. “A language L is regular if and only if there exists a left linear grammar G such that L = L(G)” P.T. “A language L is regular if and only if there exists a regular grammar G such that L=L(G)” Let h be a homomorphism & L a regular language. Then prove that homomorphic image h(L) is also regular. Prove that The set L={0i2 }I is an integer, I>=1 } which consists of all strings of 0’s whose length is a perfect square,is not regular What are the Applications of Pumping Lemma What are Decision Algorithms for Regular sets Define Emptiness, Finiteness,and Infiniteness, Equivalence Let L be any subset of 0*.Prove that L* is Regular. Show that r=(1+01)*( 0+1*) denotes the language L={w∈{0,1)*: w has no pair of consecutive zeros) find the other two expressions. Give the set and explain in English the sets denoted by following regular expressions. a) (11+0) (00+1) b) (1+01+001)(0+00) c) (0+1)00(0+1) d) 0 1 2 e) 00 11 22 Denote the regular languages defined by the following grammar as regular expressions. a) G1 = ( { S } , { a,b} , S , { S → abS | a } ) b) G2 = ( { S,S1,S2},{a,b},S,{ S → S1ab , S1 → S1ab|S2 ,
PESIT-BSC Education For The Real World
6 6 6 5* 7* 8* 8*
8 8*
8 8* 8 8 8 8 8 8 8 8 10*
10*
10
PESIT SOUTHCAMPUS S2 → a } )
39
40 41
42 43 44 45 46 47
48
49
50 51 52
Show that the family of regular languages is closed under following operations a) union b)intersection c)concatenation d)complementation e) starclosure f) difference g) reversal
10
Is the Class of Regular sets closed under infinite union What is the relationship between the class of regular sets and the least class of languages closed under union, intersection and complement Containing all finite sets Give a finite automaton construction to prove that class of regular sets is closed under substitution Prove that if two finite automata are equivalent they accept the same language Let L be the set of strings of 0’s and 1’s beginning with a1 whose value treated as a binary number is prime ,Prove that L is not regular. What are the properties of Regular sets and prove that given L is not regular with an example What are the closure properties of Regular sets Write NFA & right linear grammar for L(aab*a) Given a standard representation of any regular language L on Σ a) Prove that there exists an algorithm for determining whether or not any w ∈ Σ* is in L b) Prove that there exists an algorithm for determining whether L is empty, finite or infinite. Prove that the language L = { anbn : n ≥ 0 } is not regular using pigeonhole principle. State and prove pumping lemma for regular languages ? What is the application of pumping lemma. Using pumping lemma, prove that following languages are not regular :a) L = { anbn : n ≥ 0 } b) L = { wwr : w ∈ Σ* } Σ = { a,b} c) L = { w ∈ Σ* : na(w) < nb(w) } Σ = { a,b } d) L = { (ab)nak : n > k , k ≥ 0 } e) L = { an! : n ≥ 0 } f) L = { anbkcn+k : n ≥ 0 , k ≥ 0 } g) L = { anbl : n ≠ l } Define regular expression. Construct an NFA for the L((a+b)*abb) Show that if L is a regular language on alphabet ∑ then there exists a right linear grammar G = (V, ∑, S, P) such that L=L(G). Given the below NFA, write the corresponding regular expression using generalized transition graphs.
10 10
b
b
a,b
a Q0
b a
PESIT-BSC Education For The Real World
Q2
10 10 10 10 10* 10*
10*
10
6* 8* 10*
PESIT SOUTHCAMPUS Chapter 5 : Context free Grammars And Languages
1 2 3 4 5 6 7 8 10 11 12 13 14 15
16 17 18 19
20 21 22
23 24 25 26
27 28
Define a ambiguous CFG. Define CFG and What are its advantages Define simple grammar or s-grammar? What are its applications? Define leftmost and rightmost derivation with example. Define derivation tree, partial derivation tree, yield. Explain dependency graph & its applications in CFG. Write the regular expression for all pascal real numbers. Explain exhaustive search parsing? What is the serious flaw in using exhaustive search parsing? Prove the substitution rule of context free grammar? Find the regular expression for pascal sets whose elements are integer numbers. Let L1=L(a*baa*) and L2=L(aba*) .find L1/L2. Define inherently ambiguous language and give an example ? What are CFG’s Give CFG for the language L= {an b2n | n>0} Given the grammar G as follows: S aAS|a, AsbA|SS|ba Find the left most and right most derivation parse tree for the string aabbaa. Show that the grammar given below is ambiguous E E+E/E*E/(E)/I,Ia/b/c What are the applications of CFG Give a CFG generating the following set that is the set of palindromes over alphabet{a,b} Give a CFG for the set of all strings of balanced parenthesis, each left parenthesis has a matching right parenthesis and pairs of matching parenthesis are properly nested Define context free grammars formally. Give some examples . Let G be the grammar S->aS|aSbS|∈ prove that L(G)={x| each prefix of x has atleast as many a’s and b’s} Write CFG which generates the following CFL’s L(G) = { wwr : w ∈ Σ* } Σ = { a,b} a) L(G) = { ab(bbaa)nbba(ba)n : n ≥ 0 } b) L = { anbm : n ≠ m } c) L = { w ∈ { a , b }* : na(w) = nb(w) and na(v) ≥ nb(v) where v is any prefix of w } d) L = { a2nbm : n ≥ 0 m ≥ 0 } Let G = ( V,T,S,P) be a CFG. Then prove that for every w ∈ L(G), there exists a derivation tree of G whose yield is w. Prove that yield of any derivation tree is in L(G), where G is a CFG. If L is a regular language ,prove that the language { uv:U⊂L, v⊂LR Is also regular Find DFA’s that accepts the following languages. a) L(aa*+aba*b*) b) L(ab(a+ab)*(a+aa)) c) L((abab)* + (aaa* +b)*) d) L((a+b)*(a+b)*)) Construct parse tree for the following grammar S-> aAs|a A->SbA|SS|ba Let G=(V,T,P,S)be a CFG ,then S=>a if and only if there is a derivation tree in
PESIT-BSC Education For The Real World
2 5 5 5 5 5 5 5 5 5 5 5 5* 6*
6* 6* 5 5
5* 5 8
8* 8
8*
PESIT SOUTHCAMPUS 30 31 32 33
34 35
36 37 38 39 40 41 42 43 44 45
grammar G with yield a Construct Leftmost and Right most derivation tree for the following grammar S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa What are ambiguous grammar and inherently ambiguous grammarwith an example The grammar E->E+E|E*E|(E)|id generates the set of arithmetic expressions with +,*,Parentheses and id.Construct an equivalent unambiguous grammar. Show that every CFL without ∈ is generated by a CFG all of whose productions are of the form A->a, A->aB and A->aBC Show that every CFL without ∈ generated by a CFG all of whose productions are of the form A->a and A->aab Let G be the grammar S->aB|bA, A->a|aS|bAA,B->b|bS|aBB for the string aaabbabbba find a leftmost and right most derivation parse tree Is the grammar given in q(42) is unambiguous if it is prove it What are linear grammar show that if all productions of aCFG are of the form A>wB or A-w then L(G) is a regulars et Can every CFL without ∈ be generated by a CFG all of whose productions are of the forms A->BCD and A->a Construct a CFG for the set of all strings over the alphabet {a,b} with exactly twice as many a’s and b’s. Given the grammar G as follows S->aAS|a A->sbA|SS|ba find Leftmost derivation rightmost derivation and parse tree What are CFG’s Give a CFG for the Language L={an b2n|n>0} Define a CFG Construct a CFG for the following Language with n>=0,m>=0 L={an bm ck :n+2m=k} Define a CFG Construct a CFG for the following Language with n>=0,m>=0 L={an WWR bn : W∈ {a,b}*} Show that family of CFL is closed under union, concatenation and star closure Show that the language L= {anbncn | n≥1} is not a CFL
8* 10* 10 10*
10 10
10 10 10 10 10 10 10 10 10 10
Chapter 6 : Pushdown automata and properties of CFL
1 2 3 4 5 6 7 8 9 10 11 12 13
Define the instantaneous description of a NPDA Give the formal definition of DPDA and deterministic CFL. Define Linear Context free grammar and write the Pumping lemma for Linear Languages. Distinguish between DPDA and NPDA What are the demerits of regular languages when compared to context free languages What are the demerits of DFA (or NFA) when compared with PDA Why FAs are less powerful than the PDA’s How the Transition /move of a PDA defined State and prove pumping lemma for CFL? What is its application?. Give two reasons why finite automata cannot be used to recognize all CFL & why PDA is required for that purpose Explain the operations of a NPDA with diagram? Write a NPDA that accepts the language L = {anbn : n ≥ 0 } U { a } When do we say a CFL is accepted by NPDA. Define a) acceptance by final state.
PESIT-BSC Education For The Real World
5 5 5* 5* 5 5 5 5 8 8 8 8* 8
PESIT SOUTHCAMPUS 14 15
16 17 18 19 20 21 22
23 24 25 26 27
28
29 30
31 32
33
b) Acceptance by empty stack. Define PDA Describe the acceptance by “final State” and acceptance by “empty Stack” What does each of the following transitions represent? a. δ(p,a,Z)=((q,aZ) b. δ(p,a,Z)=(q,∈) c. δ(p,a,Z)=(q,r) d. δ(p,∈,Z)=(q,r) e. δ(p,∈,∈)=(q,Z) f. δ(p,∈,Z)=(q,∈) Give the formal definition of NPDA. Explain clearly the transition function? If L is a CFL, then there exists a Pda M such that L= N(M) If L is N(M1) for some PDA M1,then L is L(M2) for some PDA M2 If L is L(M2) for some PDA M2,then L is N(M1) for some PDA M1 When the PDA is Deterministic and when it is called nondeterministic Is the PDA to accept the Language L(M)={wCWR |W∈(a=b)*} is deterministic Construct a NPDA for the following languages a) L = { w ∈ { a,b}* : na(w) = nb(w) } b) L = { wwr : w ∈ { a,b}+ } Show that the language L = { anbn : n ≥ 0 n ≠ 100 } is context free Prove that for any CFL L(specified as CFG without λ productions), there exists a NPDA M such that L = L(M). Obtain a PDA to accept the language L(M)={W|W ∈ (a+b)* and na(W)=nb(W) i.e the number of a’s in string w should be equal to number of b’s in w What is an instantaneous description ? Explain with respect to PDA Construct a NPDA that accepts the language generated by grammar with productions a) S → aA b) S → Aabc|bB|a c) B → b d) C → c Obtain a PDA to accept the Language L*(M)={wCwR | W∈(a+b)*}Where WR is reverse of W. Show the sequence of moves made by the PDA for the string aabCbaa,aabCbab If L = L(M) for some NPDA M, then prove that L is CFL. Write the CFG for language accepted by NPDA whose transitions are given below :δ(q0,a,z) ={ (q0,Az) } δ(q0,a,A) ={ ( q0,A) } δ(q0,b,A) ={ ( q1,λ ) } δ(q1,λ,z) = { (q2,λ) } Obtain a PDA to accept a string of balanced Parentheses. The parentheses to be considered are(,),[,],{ and } Show that following languages are not context free using pumping lemma a) L = { anbncn : n ≥ 0 } b) L = { ww : w ∈ { a,b }* } c) L = { an! : n ≥ 0 } d) L = { anbj : n = j2 } Define linear CFL. State pumping lemma for Linear CFL. Obtain a PDA to accept the Language L={w|w ∈ (a,b)* and na(w) > nb(w)}
PESIT-BSC Education For The Real World
8* 8
8 8 8 8 8 10 10*
10 10*
8 10*
10
10* 10*
10 10
10
PESIT SOUTHCAMPUS 34
Construct an npda that accepts the language generated by the grammar S->aABB|aAA A->aBB|a B->bBB|A
10*
35
Construct the NPDA Corresponding to the grammar S aA, AaABC |bB|a, Bb, C c. Derive the string for the grammar and show the sequence of moves made by NPDA in Processing the same string Show that language L = { w : na(w) = nb(w) } is not linear. Design PDA for the language L={anbn |n≥0} give the trace for the input aaabbb Define an NPDA.Discuss about the language accepted by a Push down automata. Design an NPDA for the Language L={W: na(W)=nb(w)+1} Construct an NPDA that accepts the Language accepted by the grammar S->aA,A>aABC/bB/a, B->b,C->c Design a PDA for the following language L={anbn|n>=0}.give the trace for the input aaabbb Construct an NPDA Corresponding to the grammar S->aA A->aABC|bB|a B->b C->c Obtain NPDA for the language L={wwR : w in (0+1)*} Show that accessible instantaneous description for the string 001100 Construct the PDA equivalent to the following grammar S->aAA,A->aS|bS|a Show that if L is a CFL, then there is a PDA M accepting L by final state such that M has at most two states and makes no ∈ moves If L is N(M) for some PDA M, then L is a Context-free Language For the Grammar S-> aABB|aAA A->aBB|a B->bBB|A C->a Obtain the Corresponding PDA For the grammar S-> aABC A->aB|a B->bA|b C->a Obtain the Corresponding PDA What is the Procedure to convert a CFG to PDA What is application of GNF notation of a CFG? Is the PDA to accept the language consisting of balanced parentheses is deterministic What is the general procedure used to convert from PDA to CFG
10*
36 37 38 39
40 41
42 43 44 45 46
47
48 49 50
Chapter 7: Properties of Context-Free Languages. 1 2 3 4 5 6
What is a normal form & why is it required? Explain the method of Substitution with examples What is Left Recursion? How it can be Eliminated What is the need for simplifying a Grammar Define CNF of a CFG. Convert the following CFG into CNF
PESIT-BSC Education For The Real World
4 4 4 4 6 6
10* 12* 12* 12*
12* 12*
12* 12* 12 12 12
12
12 12 12
PESIT SOUTHCAMPUS
7
8
9 10 11 12
13
14 15 16 17 18 19 20 21 22 23 24 25
S bA|aB A bAA| aS|a B aBB|bS|b Eliminate Left Recursion from the following grammar E->E+T|T T->T*F|F F->(E)|id Eliminate Left Recursion from the following Grammar S->Ab|a A->Ab|Sa Is the following Grammar ambiguous S->aSb|SS|∈ Define greibach normal form convert the following grammar SAbb|a, AaaA|B, BbAb into the Greibach normal form Convert the grammar with productions S → Aba , A→ aab B → Ac to CNF. Obtain the following grammar in CNF S->aA|a|B|C A->aB|∈ B->aA C->cCD D->abd Obtain the following grammar in GNF S->aA|a|B|C A->aB|∈ B->aA C->cCD D->abd Define CNF and GNF Convert the following grammar to CNF S∼S | [s⊃S]|p|q (S being the only variable. Prove the family of CFL’s are not closed under intersection and Complementation What are ambiguous grammars and inherently ambiguous grammars, give an example for each Prove that family of CFL is closed under union, concatenation and star closure. Prove that family of CFL is not closed under intersection and complementation. Let L1 be a CFL and L2 be a regular language. Then prove that L1 INTERSECTION L2 is context free. Show that the language L = { w ∈ { a,b,c}* : na(w) = nb(w) = nc(w) } is not context free. What is CNF and GNF form Explain with an Example? Prove that for every CFG we can have an equivalent grammar using CNF notations where a language does not contain ∈ What is the general Procedure to convert a grammar into its equivalent GNF notation Convert the following grammar into GNF S->AB1|0 A->00A|B B->1A1
PESIT-BSC Education For The Real World
6
6
6 6* 8 8
8
10* 10* 10* 10 10 10* 10 10 10 10 10 10
PESIT SOUTHCAMPUS 26
27 28 29 30 31 32 33 34
Convert the following grammar into GNF A->BC B->CA|b C->AB|a State and prove Pumping Lemma for Context free Languages What are the Applications of pumping Lemma Show that L={an bn cn |n>=0} is not Context free Prove that CFLs are not closed under intersection and Complementation Prove that CFL’s are closed under Union, Concatenation, and star closure Show that L= {Ww|W ∈{a, b}*} is not Context free Show that L= {ap bq|p=q2} is not context free Show that L={an! | n>=0} is not Context free
10
10 10 10 10 10 10 10 10
Chapter 8 : Introduction to Turing machines
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
23
Define computations of a TM? Explain with diagram the operation of Turing machines? Give formal definition of Turing machine. Explain what is meant by instantaneous description of a TM? For Σ = {a,b} design a TM that accepts L = { anbn : n≥ 1 } Design a TM that accepts L = { anbncn : n≥ 1 } Define language accepted by TM? When do we say that a language is not accepted by TM? Define formally non-deterministic TM. On what basis we say that TM is transducer Define the operation of TM as transducers? Define a Turing computable function?
5 5*
What is Turing Computable Write a note on multidimensional TM. Write a note on universal TM. Obtain a Turing machine to accept the language L={0n1n|n>=1} Obtain a Turing machine to accept the language L(M)={0n1n2n|n>=1} Obtain a Turing machine to accept the language L={W|w∈(0+1)*} containing the sub string 001 Obtain a TM to accept the language containing strings of 0’s and ‘s ending with 011 Give an example of TM that never halts i.e., that goes to infinite loop? How is that represented in instantaneous description? Given two positive integers x and y, design a TM that computes x+y Design a TM that copies strings of 1’s Design a Turing machine that halts at a final state if x≥y and at a non-final state if x
5 5 5 8 8 8
PESIT-BSC Education For The Real World
5 5* 5* 5 5* 5 5 5
8 8 8 8 8 8
8
PESIT SOUTHCAMPUS 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
39 40 41 42 43 44 45 46
47 48
49
50
Design a TM that multiplies two +ve integers in unary notation Write a note on Turing Thesis. Define algorithm in terms of TM. Define equivalence of automata ? Demonstrate the equivalence of TM using simulation. Obtain a TM to accept a palindrome consisting of a’s and b's of any length Let x and y are two Positive integers .Obtain a Turing machine to perform x+y Given a string w design a TM that generates the string ww where w∈ a+ Define TM with stay on option. Prove that they are equivalent to class of standard TM? Prove that class of deterministic TM & class of non-deterministic TM are equivalent. Explain what do you mean by countable , uncountable sets and enumeration procedure? Prove that set of all TM, although infinite is countable Define linear bounded automata(LBA)? When do we say that a string is accepted by a LBA? Find a LBA that accepts the language L = { an! : n≥ 0 } Define TM with semi-infinite tape & prove that they are equivalent to class of standard Turing machine. Define offline TM & prove that they are equivalent to class of standard TM. Construct a TM that stays in the final state qf whenever x>=y and non-final state qn whenever x
PESIT-BSC Education For The Real World
8 8 8 8 8 8 8 8 8* 8 8* 10 * 10 10 * 12
12 12 12 12 12 12 12 15 *
15 20 *
20 *
20
PESIT SOUTHCAMPUS Off-line Turing machine
Chapter 9 : Undecidability.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Define unrestricted grammar. Explain what is Undecidability Define a recursively enumerable language & a recursive language? Define computability and decidability What are Recursive and Recursively Enumerable Languages What is the need for reducing one undecidable problem to other? Define Valid and Invalid Computation of TM's Discuss the properties of Recursive Enumerable Languages Discuss the Properties of Recursively Enumerable Languages What is the modified version of PCP What are Universal Turing Machines Define Non recursively enumerable Language Define Universal Language Give convincing arguments that any language accepted by an off line Turing machine is also accepted by some standard machine. Prove that Language Lu is Recursively Enumerable
2 5 5 5 5 5 5 5 5 5 5 5 5 8 8
17
Let S be an infinite countable set. Then prove that its power set 2S is not countable. Discuss on Rice’s Theorem and Undecidable Problems
18
Prove that Language Lu is not Recursive
8
19
Discuss the properties of R.E sets which are not r.e
8
20
Discuss Rice’s theorem for Recursive index sets
8
21
Discuss the problems about Turing Machine
8
22
If PCP were decidable, then MPCP would be decidable that is MPCP reduces to PCP
8
23
Discuss the properties of R.E sets which are R.E
8
24
What is the Undecidability of PCP
8
25
Discuss the Application of PCP
8
26
Prove that PCP is Undecidable
8
27
What is the Undecidability of Post Correspondence Problem
8
28
Prove that a language generated by an unrestricted grammar is recursively enumerable. Discuss the Rice’s theorem for recursively enumerable index sets Give the procedure for writing an unrestricted grammar which accepts the language accepted by a given TM. Prove that for every recursively enumerable language L there exists an unrestricted
8
16
29 30 31
PESIT-BSC Education For The Real World
8* 8
8 8* 8*
PESIT SOUTHCAMPUS 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49
50 51
grammar G such that L = L(G). Prove that The Complement of a Recursive Language is Recursive Prove that The union of two recursive Language is Recursive Prove that The Union of two recursively enumerable Languages is recursively enumerable Write a note on Chomsky Hierarchy If a Language L and its complement are both recursively enumerable then l and its complement is recursive Explain state entry problem & blank tape halting problem. How can halting problem be reduced to above problems? Define a context sensitive grammar? Why it is called non-contracting? Define context sensitive language? What is meant by Halting problem of Turing machine? Explain the blank tape halting problem Write a detailed note on The Chomsky hierarchy, Linear bounded automata, Post Correspondence Problem Write a CSG for language L = { anbncn : n≥ 1 } For every CSL not including λ, prove that there exists some linear bounded automaton M such L = L(M). Prove the the converse also Prove that 1) Every CSL L is recursive. 2) There exists a recursive language that is not context sensitive. Prove that it is Undecidable for arbitrary CFG’s G1 and G2 whether L(G1)intersection L(G2) is empty. Define & Explain TM halting problem? Prove that halting problem is undecidable? Prove that it is undecidable for any arbitrary CFG G whether L(G)=∑* What are the Applications of Greibach’s theorem A Turing machine is one that cannot change a non blank symbol to a blank. Which can be achieved by restriction that δ(qi,a)=(qi,€,L or R). Then a must be €.show that no generality is lost by making such a restriction. Write short notes on: a) Application of Finite Automata b) Linear Bounded automata c) Turing Machine Halting Problem d) Chomsky Hierarchy. Prove that It is undecidable for arbitrary CFG’s G1 and G2 whether Complement L(G1) is a CFL and L(G1) intersection L(G2) is a CFL Write short notes on the following: a) Chomsky hierarchy b) Unrestricted grammar c) Post correspondence problem d) Linear bounded automata
ASSIGNMENT – 1 1. Consider the given NFA and check whether the strings w=01001 and v=010101 are accepted or not. States
0
1
PESIT-BSC Education For The Real World
8 8 8 8 8 8 10 10 10 10* 10 10 10 10 10 10 10
20*
20 4*5 =20 *
PESIT SOUTHCAMPUS q0
{q0, q3}
{q0, q1}
q1
Ø
{q2}
*q2
{q2}
{q2}
q3
{q4}
Ø
*q4
{q4}
{q4}
2. Convert the following NFA to its equivalent DFA. States p
0
1 {p, q}
{p}
q
{r}
{r}
r
{s}
Ø
*s
{s}
{s}
3. Construct a NFA accepting the strings over ∑ = {a, b} and ending in aba. Use it to construct a DFA accepting the same set of strings. 4. Construct a DFA that will accept strings on ∑ = {a, b} where the number of b’s divisible by 3.Check whether the string abbbabbba is accepted or not. 5. Construct a DFA equivalent to the NFA N=({p,q,r,s},{0,1},δ, p,{ q,s}), δ defined as States 0 1 p {q, s} {q} *q
{r}
{q,r}
r
{s}
{p}
*s
Ø
{p}
6. Construct a NFA transition diagram and its equivalent DFA for M = ({qo,q1, q2},{a,b}, δ, qo,{q2}) where δ(qo,a)= {qo,q1}, δ(qo,b)= {q2}, δ(q1,a)= {qo}, δ(q1,b)= {q1}, δ(q2,a)= Ø, δ(q2,b)= {qo,q1}. 7. Convert the given NFA with ε move to its equivalent DFA.
ε Start
q1
0
q0
q3 ε
q2
1
PESIT-BSC Education For The Real World
1
q4
PESIT SOUTHCAMPUS
8. Convert the NFA with ε moves to NFA without ε moves.
a
Start
a
b
p
q
ε b
ε c
ε r a
9. (i)Convert NFA with ε moves to NFA without ε moves. (ii) Convert the ε-NFA to DFA
0 Start
1
2
ε
q2
ε
q0
q1
10. Find the ε-closure for all the states in the following ε-NFA.
q4
ε Start
q0
a
q1
b
a
q5
ε
ε q2
ε q3
q8 ε q6
q7
ε
b 11. Construct a DFA that accepts all the strings on Σ = {0,1} except those containing the substring 101. 12. Construct a DFA having set of all strings over the alphabet Σ = {a,b}whose last two symbols are the same. 13. Construct an equivalent DFA for the following NFA.
0,1 0
q1
PESIT-BSC Education For The Real World
0,1
q9
PESIT SOUTHCAMPUS 0
Start
q0
q3 1
q2
1
14. Construct an equivalent DFA for the following NFA.
a
b Start
a
q0
q1
a a
a
b
q2 a 15. Construct an equivalent NFA without ε moves.
a Start
a
q0
q1
a
b ε
q2
a,b
ε q3
q4
16. Construct DFA for the following NFA. Let M=({q0, q1}, {0,1},δ, q0, {q1}) where δ(q0,0)={q0, q1}, δ(q0,1)={q1}, δ(q1,0)= Ø, δ(q1,1)={q0,q1}. 17. Construct a DFA having even no. of b’s where Σ = {a,b}. 18. Convert the the following NFA’s to DFA’s.
p
0 {p, q}
1 {p}
*q
{r,s}
{t}
r
{p,r}
{t}
*s
Ø
Ø
*t
Ø
Ø
19. Construct a finite automata that accepts the set of all strings in {a,b,c}* such that the last symbol in input string appears earlier in the string.
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS ASSIGNMENT – 2 1. Construct a NFA equivalent to the regular expression ((10)+(0+1))*01. 2. Convert the following DFA to regular expression.
Start
0
q1
1
q2
q3
3. Construct the transition diagram of a finite automata corresponding to the regular expression. (ab+c*)*b 4. Find the regular expression for the set of all strings denoted by R223 from the DFA.
Start
1
1
1
2
3
5. Construct a Regular expression to the transition diagram.
0 Start
1
1
q1
q2
0
0
1
q3
6. Construct a NFA for the regular expression (a/b)*abb and draw its equivalent DFA. 7. Find the Regular Expression corresponding to the Finite Automata.
0 Start
q0
1 1
q1
0,1 0
PESIT-BSC Education For The Real World
q2
PESIT SOUTHCAMPUS 8. Construct a minimum state automaton equivalent to a given automaton M where transition table is States q0
a q0
B Q3
q1
q2
q5
q2
q3
q4
q3
q0
q5
q4
q0
q6
q5
q1
q4
*q6
q1
q3
9. Show that the language L = {0p , p is prime} is not regular. 10. Construct regular expression for a(a+b)*a into ε-NFA and find minimal state DFA. 11. Construct a NFA for the regular expression (0+1)*0(0+1) and draw its equivalent DFA. 12. Find whether the languages are regular a) L = {w Є (a,b) | w=wR } b) L = { 0n 1m 2m+n | n,m ≥1} 13. Let G be the grammar S→aB/bA, A→a/aS/bAA, B→b/bS/aBB. For the string aaabbabbba find the leftmost derivation and also obtain the parse tree. 14. Write a Grammar to recognize all prefix expressions involving all binary arithmetic operators. Construct parse tree and also give the leftmost and rightmost derivation for the sentence “-*+abc/de” using the constructed grammar. 15. Show that the grammar S→a/Sa/bSS/SSb/SbS is ambiguous. 16. Find a derivation tree of a*b+a*b given that a*b+a*b is in L(G) where G is given by S→S+S/S*S/a/b. 17. Find L(G) where G = ({S},{0,1},{S→0S1/ε},S). 18. Let G be the grammar S→OB/1A, A→0/0S/1AA, B→1/1S/0BB. For the string 00110101 find its leftmost derivation and derivation tree. 19. Show that E→E+E/E*E/(E)/id is ambiguous. Show that id+id*id have two distinct leftmost derivation.
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS 20. Show that the grammar S→aSbS/bSaS/ε is ambiguous and give the language generated by this grammar.
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS ASSIGNMENT – 3 1. Design a PDA that accepts the language of the grammar. S→AB, A→aA/ε, B→aBb/ε and check for the string aaaabb. 2. Convert the grammar S→0S1/A, A→1A0/S/ε to a PDA that accepts the same language by empty stack. 3. Convert the grammar S→aAA, A→aS/bS/a to a PDA that accepts the same language by empty stack. 4. Consider the grammar G=(V,T,P,S) where S→aA, A→aABC/bB/a, B→b, C→c.Find the PDA and process the string aaabc 5. Convert the PDA P=({q,p},{0,1},{Z0,X}, δ,q, Z0,{p}) having the following
transition
function
δ(q,0,
Z0)={(q,XZ0)},
δ(q,0,
X)={(q,XX)}, δ(q,1, X)={(q,X), δ(q, ε, X)={(p, ε)}, δ(p, ε, X)={(p, ε)}, δ(p,1, X)={(p,XX), δ(p,1, Z0)={(p,
ε)}to a
Context
Free
Grammar. 6. Let M =({q0, q1},{0,1},{Z0,X}, δ, q0, Z0) where δ is given by δ(q0,0, Z0)={(q0,XZ0)}, δ(q0,0, X)={(q0,XX)}, δ(q0,1, X)={(q1, ε), δ(q1, 1, X)={(q1, ε)}, δ(q1, ε, X)={(q1, ε)}, δ(q1, ε, Z0)={(q1, ε)}construct a CFG G=(V,T,P,S) generating N(M). 7. Construct a PDA accepting { anbman|m,n≥1} by empty stack. Also construct the corresponding CFG accepting the same set. 8. Construct a CFG accepting {ambn|n
a
CFG
q1},{a,b},{Z0,Z},
G δ,
which q0,
Z0)
accepts where
N(M) δ
is
where
given
M=({q0,
by
δ(q0,b,
Z0)={(q0,ZZ0)}, δ(q0, ε, Z0 )={(q0, ε)}, δ(q0,b, Z)={(q0, ZZ), δ(q0,a, Z)={(q1, Z)}, δ(q1,b, Z)={(q1,ε)}, δ(q1,a, Z0)={(q0, Z0)}. 10. Consider the PDA with transitions, δ(q0,a,Z)={(q0,AZ)}, δ(q0,a, A)={(q0,A)}, δ(q0,b, A)={(q1, ε )}, δ(q1, ε, Z)={(q2, ε)}find the equivalent CFG. 11. Find a grammar in Chomsky Normal Form equivalent to S→aAbB, A→aA/a, B→bB/b. 12. Find a grammar in CNF equivalent to S→aAD, A→aB/bAB, B→b, D→d.
13. The grammar has the productions S→0A0/1B1/BB, B→C/S/A, C→S/ε i) Eliminate the ε productions ii) Eliminate the unit productions iii) Eliminate the useless symbols iv) Convert into CNF.
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS 14. Find a CFG with no useless symbols equivalent to S→AB/CA, B→BC/AB, A→a, C→aB/b. 15. Find the equivalent CNF for the above grammar.
16. Obtain the CNF equivalent to the grammar S→bA/aB, A→bAA/aS/a, B→aBB/bS/b. 17. Convert the Grammar into CNF A→bAB/ ε, B→BAa/ ε. 18. Construct the equivalent GNF for the CFG, G = ({A1, A2, A3},{a,b}, P, A) where P consists of A1→ A2A3, A2→ A3A1/b, A3→ A1A2/a. 19. Convert the given grammar to GNF S→aSb/ab. 20. Design a deterministic turing machine to accept the language L={aibici|i≥0}
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS Objective type questions 1. Automata in which the output depends on the transition and current input is called ________machine. a) Moore b) Mealy c) Finite state d) Turing 2. Can a DFA simulate NFA? Yes/No. 3. What are the components of finite automata model? a) I/p tape, read head, finite control b) I/p tape, stack c) I/p, finite control d) finite control. 4. The recognizing capability of NFA and DFA ____________. a) may be different b)must be different c) must be same d) none of these. 5. Give English description of the languages for the regular expression a*b+b*a. 6. A regular expression is a ___________ that describes the whole set of strings according to certain syntax rules. a) symbol b) string c) grammar d) language. 7. Arden’s theorem helps in checking the __________ of two regular expressions. a) equivalence b) difference c) union d) concatenation. 8. The ________ of the programming language can be expressed using regular expressions. a) table b) grammar c) language d) tokens 9. Regular expression (a|b)(a|b) denotes the set. a) {a,b,ab,aa} b) {a,b,ba,bb} c) {a,b} d) {aa,ab,ba,bb} 10. Let a and b be regular expressions then (a* U b*)* is equivalent to _________. a) (a U b)* b) (b* U a*)* c) (b U a)* d) a U b 11. The recognizing capability of NDFA and DFA ________. a) may be different b) must be different c) must be same d) none of the above. 12. The logic of pumping lemma is a good example of ____________. a) pigeon hole principle b) divide and conquer strategy c) recursion d) iteration.
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS 13. A grammar is said to be ambiguous if it has more than one _______ for a string. a) Leftmost derivation b) Rightmost derivation c) Parse tree d) all the above. 14. The languages accepted by a PDA by empty stack and final states are different languages. True/False. 15. The number of auxiliary memory required for a Pushdown Automata to behave like Finite automata is______ a) 2 b) 1 c) 0 d) 4. 16. A PDA behaves like a TM when number of auxiliary memory it has is ___________. a) 2 b) 1 c) 0 d) 4. 17. The language {ambmcm|m≥0}is a context free language. True/False. 18. CFL are not closed under intersection and complementation. True/False. 19. Consider the grammar S→PQ|SQ|PS, P→x, Q→y to get a string of n terminals the number of productions to be used is __________. a) n2 b) n+1 c) 2n d) 2n-1. 20. The CFG S→aS|bS|a|b is equivalent to the regular expression. a) (a*+b*)* b) (a+b)* c)(a+b)(a+b)* d) (a+b)*(ab)* 21. The CFG S→aB|bA, A→b|aS|Baa, B→b|bS|aBB generates the string of terminal that have _______. a) equal no. of a’s and b’s b) odd no. of a’s and odd no. of b’s c) even no. of a’s and even no. of b’s d) odd no. of a’s and even no. of a’s. 22. The intersection of a CFL and a regular language __________. a) need not be regular b) need not be context free c) is always regular d) is always context free. 23. Give the tuple representation of a Turing machine. 24. A TM is more powerful than FA because _______. a) tape movement confined to one direction b) it has no finite state c) it has the capability to remember arbitrary relay long sequence of input symbols d) none of these. 25. A TM can’t solve halting problem. True/False. 26. Complement of a recursive language is recursive. True/False. 27. The number of internal states of a UTM should be at least________. 1 b) 2 c) 3 d) 4.
PESIT-BSC Education For The Real World
PESIT SOUTHCAMPUS
PESIT-BSC Education For The Real World
