Give a Context Free Grammar for the following language. i) L1={ai bj ck | i = j + k} such that i, j, k > 0 ii) L2={ai bj ck | j = i + k} such that i, j, k > 0

Reduce the following grammar to Greibach Normal form. SSS, S0S1 01

Show that the following grammar is ambiguous. S-> iCtS S-> iCtSeS S-> a C-> b

Convert the following grammar to Chomsky Normal Form (CNF). G=({S}, {a,b}, P,S) P={S  aSa | bSb | a | b | aa | bb}

Consider the following grammar. E -> E + E | E – E | id Derive the string id-id*id using i) Leftmost derivation ii) Rightmost derivation

Find the transition rules of PDA for accepting a language L={w {a,b}*|w is of the an bn with n 1}through both empty stack and final state and demonstrates the stack operation for the string aaabbb.

Design a push down automation to recognize the language generated by the following grammar : SS + S | S  S | 4 |2 Show the acceptance of the input string 2+2*4 by this PDA.

What is NPDA? Construct a NPDA for the set of all strings over {a,b} with odd length palindrome.

Design a push down automation to recognize the language generated by the following. SS + S | S  S | 4 |2 Show the acceptance of the input string 2+2*4 by this PDA.

Design a Turing Machine for the following language by considering transition table and diagram. i) TM that erases all non blank symbols on the tape where the sequence of non blank symbols does not contain any blank symbol B in between. ii) TM that find 2’s complement of a binary machine.

What is TM? Design TM to check well formedness of parenthesis. Expand the transition for (()) ()

How turing machine can be use to compute the functions? Design turing machine for multiplication of two numbers.

Elaborate the following terms. i) Universal Turing Machine (UTM) ii) Recursively Enumerable Languages iii) Halting problem of Turing Machine

Define and Compare Class P and Class NP Problem with suitable diagram.

What do you mean by polynomial time reduction? Explain with suitable example.

Explain Satisfiability Problem and SAT Problem and comment on NP Completeness of the SAT Problem.

What makes a problem NP-Complete? How do we prove a problem is NP-complete? Are all decision problems NP-complete?

What is context free Grammar? Define CFG. What are the capabilities of CFG? Give a context Free Grammar for the following language L = {w | w is a palindrome of odd length, w ∈ {a,b}*}

i) What is Derivation in CFG? ii) What is relation of parse tree for derivation in CFG? iii) What is leftmost derivation and Rightmost derivation? iv) Explain leftmost derivation and Rightmost derivation with parse tree. Derive the string a-b+c using leftmost derivation and Rightmost derivation for the CFG having production rule. G = {S = S + S; S = S - S; S = a | b | c}

When do we say that CFG is in Greibach Normal Form (GNF)? Explain the steps to convert CFG to GNF for following Grammars: G1 = {S → aAB | aB, A → aA | a, B → bB | b}; G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}; G3 = {S → XB | AA; A → a | SA; B → b; X → a}

i) What is ambiguity in CFG? What is relation of parse tree for finding ambiguity in CFG. ii) What is leftmost derivation and Rightmost derivation? iii) Explain leftmost derivation and Rightmost derivation and ambiguity for the CFG having production rule. G = { S = aSb | SS; S = ε}

What is pushdown automata? Define PDA pictorially and mathematically with respect to input tape, stack, finite control and Instanteous description. Design a PDA for accepting a language {anb2n|n>=1}

Construct a context free grammar which accepts N (A), where A = ({q0, q1}, {0, 1}, {Z0, Z}, , q0, Z0, ) where  is given by: (q0, 1, Z0) = {(q0, Z Z0)}; (q0, ε, Z0) = {(q0, ε)}; (q0, 1, Z) = {(q0, Z Z)}; (q0, 0, Z) = {(q1, Z)}; (q1, 1, Z) = {(q1, ε)}; (q1, 0, Z0) = {(q0, Z0)}

Design a PDA for accepting a language {0n1m0n | m, n>=1}.

Draw a PDA for the CFG given below: S → aSb; S → a | b | ε. And simulate PDA to recognize “aaabb”.

Design a push down automation to recognize the language generated by the following grammar: S → S + S | S * S | 4 | 2. Show the acceptance of the input string 2 + 2*4 by this PDA.

Elaborate the following terms with proper examples: i) Universal Turing Machine (UTM) ii) Recursively Enumerable Languages

Design a TM that multiplies two unary numbers over  = {1}. Write simulation for the string 11*111.

Construct a TM for the language L = {0n1n2n} where n≥1.

Construct a TM for substraction of two unary numbers f(a-b) = c where a is always greater than b.

What is undecidability? How do we prove universal language is undecidable? What is the relation between undecidability and reducibility theory.

What do you mean by polynomial time reduction? Explain with an example of SAT.

Explain the following terms with respect to computations complexity with example: i) Solvable Vs Unsolvable problem ii) Decidable Vs. Undecidable problem iii) P Vs NP problem

Explain in brief the term “recursively enumerable”.

Explain examples of problems in NP.

Differentiate between P class and NP class.

Give Context Free Grammars for the following languages and show the derivation for given string. i) L={ w {a,b}*|w is string of staring with ‘a’ and ending with’ b’ } show the derivation for “ababab” ii) L = anb2n where n>=1. Show the derivation for “aabbbb” iii) RE= (0+1)* Show the derivation for “0110”

Reduce the following grammar to Greibach Normal form. S  AA | 0 A  SS | 1

Convert the following grammar to CNF. S  aSa | bSb | A |  A a | b | 

In the grammar, convert the given production rule into GNF form. If any production rule in the grammar is not in GNF form, convert it. S  XB | AA A  a | SA B  b X  a

i) Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA. S  0BB B  0S | 1S | 0 ii) Construct PDA for the given CFG, and test whether ‘aaabb’ is acceptable by this PDA. S  aSb S  a | b | 

Construct PDA to accept L= { anbn | n>= 1 } through empty stack.

Convert the given PDA to CFG S->0S1 | 00 | 11

Construct Pushdown automata for L = {0n1m2(n+m)| m,n  0}

NPDA for accepting the language L = {a2mb3m | m  1}

NPDA for accepting the language L = {aibjckd1 | i==k or j==1,i>=1,j>=1}

Write short notes on with suitable diagrams. i) Reducibility ii) Multi-tape Turing Machine iii) Multi-head Turing Machine iv) Two-way infinite Tape Turing Machine: v) Multi-tape Multi-head Turing Machine

Construct a TM for subtraction of two unary numbers f(a-b) = c where a is always greater than b. Explain the logic of building this Turing machine.

Draw a Turing Machine to increment a binary number by 1 and demonstrate with any example.

Obtain a Turing Machine to accept the language containing strings of a’s and b’s that do not end with abb.

Construct a TM for the language L = {0n1n2n} where nl

What Minimum spanning tree problem? Prove that finding MST by using Kruskal’s algorithm is in class P.

What is post correspondence problem? Why is post correspondence problem undecidable? Explain PCP with following instance of the set of the strings A and B. A: 1, 10111, 10; B: 111, 10, 0

Define and Compare Class P and Class NP Problem with suitable diagram.

State and explain with suitable example. i) Decidable Problem ii) Undecidable Problem iii) Church-Turing Thesis

Convert the following grammar to Chomsky Normal form (CNF) S→a | aA | B A→aBB | ε B→Aa | b

Convert the following grammar to GNF. S→XB | AA A→a | SA B→b X→a

Show that the following grammar is ambiguous. S-> iCtS S-> iCtSes S-> a C-> b

Convert the following grammar to chomsky normal form (CNF) G=({S}, {a, b}, P, S) P = {S→aSa | bSb | a | b | aa | bb}

Consider the following grammar. E-> E + E | E–E | id Derive the string id-id*id using i) Leftmost derivation ii) Rightmost derivation.

Find the transition rules of PDA for accepting a language L={w∈{a,b}* |w is of the anbn with n≥1} through both empty stack and final state and demonstrates the stack operation for the string aaabbb.

Design a PDA for accepting a language {anb2n | n>=1} Simulate this PDA for the input string “aaabbbbbb”.

Design a PDA for accepting a language {0n1m0n | m, n>=1}. Simulate this PDA for the input string “0011100”.

Construct a PDA for L= {0n1m2m3n | m,n≥0}

Compare FA and PDA.

Write a short note on Halting problem of Turing machine.

Design a Turing Machine for the following language by Considering transition table and diagram. i) TM That erases all non blank symbols on the tape where the sequence of non blank symbols does not contain any blank symbol B in between. ii) TM that find 2’s complement of a binary machine.

Design a Turing Machine that reads a string representing a binary number and erases all leading 0’s in the string. However, if the string comprises of only 0’s it keeps one 0.

Write short notes on: i) Reducibility ii) Multi-tape Turing Machine

Construct a Turing Machine for R=aba*b

Design a TM that multiplies two unary numbers over Σ={1}. Write simulation for the string 11*111.

Justify “ Halting problem of Turing machine is undecidable”

Define and compare class P and class NP problem with suitable diagram

Explain in brief the term “recursively enumerable”.

Explain examples of problems in NP.

Differentiate between P Class and NP class.

Check whether the string 10010 is a member of the language generated by following grammar by using Cocke-Younger-Kasami Algorithm- S -> AB|BC, A -> BA|0, B -> CC|1, C -> AB|0

Obtain grammar to generate the following language : L = {w : na(w) mod 2=0 where w {a, b}*} i.e. Language of a and b in which number of number of a’s in the string is either zero or in multiple of 2 only.

S -> aB|bA, A -> a|aS|bAA, B -> b|bS|aBB Derive using Leftmost Derivation and Rightmost Derivation: i) bbaaba ii) aaabbb. Draw parse tree for the same.

Find context Free Grammar generating each of these languages. i) L1={ai b j ck such that i = j+k where I, j, k > = l} ii) L2={ai b j ck such that j = i+k where I, j, k > = l}

Construct a PDA equivalent to following CFG i) X -> 0X, X -> 1XX, X -> XX1, X -> X1X ii) S -> BD|BC, D -> SC, C -> AA, B -> 0, A -> 1

Design a PDA for a language L={anb2n|n > =1}

Construct a PDA accepting the language L= a n b m a n | n,m>=0 by null store.

Design a PDA for a language L={XcX r |X€{a,b}* and string Xr is the reverse of string X}.

Obtain a PDA to accept the language - L= {w|w€{a,b}*, na(w)=nb(w)} by final state

Design a Turing machine for well formed parenthesis.

Design a TM that accepts all strings over {1,0} with even number of 0’s and even number of 1’s.

Construct TM that recognizes language over alphabet 0,1 such that string ends in 10.

Construct a TM to accept the language over {0,1} containing the substring 001.

Design a TM to multiply a unary number by 2.

Design Turing Machine for l’s Complement.

What is post correspondence problem? Explain PCP with following instance of the set of the strings A and B.

State and explain with suitable example i) Decidable Problem ii) Undecidable Problem iii) Church-Turing Thesis.

What is reducibility in Computability Theory ? Explain in detail, the polynomial - time reduction approach for proving that a problem is NP-Complete.

Explain with suitable example and diagrams i) Halting problem of TM ii) Multitape TM iii) Universal TM

Give Context Free Grammars for the following languages i) L={ w  {a,b}*|w is string of staring with ‘a’ and ending with ‘b’} ii) RE = 0(0+1)*01(0+1)*1 iii) RE = (011+1)* (01)*

Simplify the following grammar as i) Eliminate Useless production S -> abS | abA | abB A -> cd B -> aB C -> dc ii) Eliminate Unit Production S -> Aa | B A -> b | B B -> A | a iii) Eliminate the  Production S XYX X 0X |  Y  1Y | 

S  aB | bA A  a | aS | bAA B  b | bS | aBB Derive using Leftmost Derivation and Rightmost Derivation : i) bbaaba ii) aaabbb. Draw parse tree for the same.

Find context Free Grammar generating each of these languages. i) L1 = { aibjck such that i = j + k where I, j, k>=1} ii) L2 ={ aibjck such that j = i + k where I, j, k>=1}

i) Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA. S 0BB B  0S | 1S | 0 ii) Construct PDA for the given CFG, and test whether ‘aaabb’ is acceptable by this PDA. S aSb S  a | b | 

What is NPDA? Construct a NPDA for the set of all strings over {a, b} with odd length palindrome.

Construct a PDA accepting the language L ={anbman|n,m >=0}by null store.

Design a PDA for a language L={XcXr | X € {a,b}* and string Xr is the reverse of string X}

Obtain a PDA to accept the language - L = {w | w € *,  = {a, b} and na(w) = nb(w)}by final state

Design the Turing for the function f(n) = 2n is computable.

What are the different ways for extension of TM? Explain. Design TM for language L={ambn | m < n}

Construct a TM to accept the language over {0,1} containing the substring 001.

Design a TM to multiply a unary number by 2.

Design Turing Machine for l’s Complement.

What Traveling salesman problem? How to prove that Traveling salesman problem is NP Complete?

What is post correspondence problem? Why is post correspondence problem undecidable? Explain PCP with following instance of the set of the strings A and B A B 1. 1 111 2. 10111 10 3. 10 0

What is reducibility in Computability Theory ? Explain in detail, the polynomial time reduction approach for proving that a problem is NP- Complete.

State and explain with suitable example : i) Decidable Problem ii) Undecidable Problem iii) Church-Turing Thesis.

Design DFA which accepts set of strings over alphabet {a, b} such that i) if it contains exactly 3 number of a’ s. ii) if it contains at least 3 number of a’ s.

Consider the following Mealy Machine of Construct equivalent Moore machine. Also differentiate between Moore and Mealy machine (any 4 points).

Design Moore machine such that for every substring that ends in bab the machine will give output 1 over alphabet  {0, 1}. Further convert the same Moore machine into Mealy machine.

Design a DFA which can accept a binary number divisible by 3. Explain the logic also.

Write a regular expression to accept following language over alphabet {a,b}* i) Strings having at least one occurrence of substring ‘aaa’. ii) Strings starting and ending with same symbol. iii) Strings having even number of a’ s.

Using Arden’s theorem, find regular expression.

Draw NFA with epsilon Moves for RE = (a*+b*)

Check the equivalence of the Regular Expression. i) (a*bbb)*a* & a*(bbba*)* ii) ((a+bb)*aa)* & E+(a+bb)*aa

Describe the languages accepted by the following regular expression and justify. i) a (a + b) * ab ii) (1 *01*01*)*

Show that L = {an |n is a prime} is not regular.

Convert the given NFA–ε to an NFA to DFA.

Define Pumping Lemma and apply it to prove the following L={0m1n0m+n | m>=1 and n>=1} is not regular

Convert following NFA to DFA

Design a Mealy machine that accepts strings ending in ‘00’ or ‘11’. Convert the Mealy machine to the equivalent Moore machine

Convert the following RE to ε–NFA and find the ε–closure of all the states and corresponding DFA. (0+1)*. 1.(0+1)

• The set of strings over {0,1} that have at least one 1. • The set of strings over {0,1} that have at most one 1. • The set of all strings over {0,1} ending with 00 and beginning with 1.

Consider the two RE r=0*+1*, s=01*+10*+1*0+(0*1)* i) Find the string corresponding to r but not to s. ii) Find the string corresponding to s but not to r. iii) Find the string corresponding to both r & s. iv) Find the string corresponding to neither r nor s.

Write regular expressions for the following languages over the alphabet ∑={a,b} i) All strings that do not end with ‘aa’. ii) The set of all strings ending neither in b nor in ba iii) Find the shortest string that is not in the language represented by the regular expression a*(ab)*b*.

Draw FA for the following language over {0. 1} i) Number of 1’s is multiple of 3. ii) Number of 1’s is not multiple of 3

Covert following NFA into equivalent DFA and perform DFA minimization Q/Σ 0 1 → P {P, Q} {P} Q {R} {R} R {S} -- S* {S} {S}

Construct DFA for checking “whether a string over alphabet {a, b} contains a substring aba”.

i) Differentiate between Moore machine and Mealy machine. ii) Construct Moore machine equivalent to the following Mealy machine. (Show it in transition Diagram) M = (Q, Σ, Δ, δ, q0) where Q = {q0, p0, p1), Σ = {0, 1), Δ = {y. n} and δ is shown as given below. Input / Output States 0 1 q0 p0/n p1/n P0 p0/y p1/n P1 p0/n p1/y

Convert the following DFA to its Minimized form (Minimization of DFA).

Prove that LHS RE is equivalent to RHS RE (1+00*1)+(1+00*1)(0+10*1)*(0+10*1) =0*1(0+10*1)*

Find a regular expression corresponding to each of the following subsets of {0,1}* i) The language of all strings containing exactly two zeros ii) The language of all strings containing at least two zeros iii) The language of all strings that do not end with 01.

Write a note on Myhill Nerode theorem.

Construct Regular expression for following DFA using Ardens theorem.

i) Write regular expression for a set of strings of 0s and 1s with even number of 0s. ii) Write regular expression for a set of strings of 0s and 1s containing odd number of 1s.

Choose any one option given below and give the justification “The regular expression 0*(10*)* denotes the same set as” i) (1*0)*1* ii) 0+(0+10)* iii) (0+1)* 10(0+1)* iv) none of these

Convert the given NFA-ε to an NFA to DFA.

Design a DFA which can accept a decimal number divisible by 3.

Convert following NFA to DFA.

i) Design a moore machine for the 1’s complement of binary number. ii) Design a Mealy machine to find out 2’s complement of a given binary number.

Convert the following RE to ε-NFA and find the ε-closure of all the states and corresponding DFA. (0 + 1) *.1.(0 + 1).

i) Regular Expression of strings over {0,1} that have at least one 1. ii) Regular Expression of strings over {0,1} that have at most one 1. iii) Regular Expression of all strings over {0,1} ending with 00 and beginning with 1.

i) Write the regular expression for the language starting with a but not having consecutive b’s. ii) Write the regular expression for the language L over ∑ = {0,1} such that all the string do not contain the substring 01. iii) Write the regular expression for the language containing the string over {0,1} in which there are atleast two occurrences of 1’s between any two occurrences of 1’s between any two occurrences of 0’s.

Design a FA from given regular expression 10 + (0 +11) 0 *1.

Construct the regular expression for the given DFA using Ardens Theorem.