Theory of Computation — Summer 2019

Define 1) Parse tree 2) Ambiguous grammar

Prove by mathematical induction: for every n>=1, 1 + 3 + 5 + … + (2n - 1) = n2

Consider the grammar: SABA, AaA | , BbB |  Is given grammar ambiguous? If so then remove ambiguity

Design Moore machine to generate 1’s complement of binary number.

Write Regular Expression over the alphabets {a, b} consisting strings:  Second last character as ‘a’  Starting with ‘a’ and ending with ‘b’

Find context free grammar for the following language. L ={aibjck | i = j + k}, L = (011+1)* (01)*, L =(0+1)1*(1+(01)*)123

Draw FA for following languages:  L1 = {w | 00 is not substring of w}  L2 = {w | w ends in 01} Find FA accepting languages (i). L1  L2 and (ii). L1  L2

Give the left linear grammar for RE (10)*1

Minimize the given DFA: State / Transition a b  1 {3} {2} 2 {4} {1} 3 {5} {4} 4 {4} {4} 5 {3} {2}

Eliminate useless symbols, -productions and unit productions for the following grammar: S0A0 | 1B1 | BB, AC, BS | A, CS | 

Consider the grammar: S  aAS | a A  SbA | SS | ba Derive left most and right most derivation of string aabbaa using given grammar.

Give CFG for following languages: 1). L = a*b* 2). L = {an+2 bn | n >= 0}

Construct finite automata for following left linear grammar: S  X0 | Y11 X  Y1 Y  Y0 | 1

Compare PDA with FSM

Write a note on DPDA and NPDA

Design a pushdown automata to check well-formed parenthesis.

Give the formal definition of Turing machine. Also compare the power of DFA, NFA, DPDA, NDPA and TM

Write a note on post machines.

Design a Turing machine to reverse the string over alphabet {0, 1}

Compare and contrast push down automata and Turing machine.

Enlist limitations of Turing machines.

Design a Turing machine which accepts the language consisting string which contain aba as a substring over alphabets {a, b}

Discuss universal Turing machine

Write a short note on Halting problem

What is decidability? How to prove that the given language is undecidable? List some undecidable problems.