UNIT-V UNDECIDABILITY

1 When a recursively enumerable language is said to be recursive.
2 Is it true that the language accepted by a non deterministic Turing Machine is different from recursively enumerable language?
3 When we say a problem is decidable? Give an example of undecidable problem?
4 Give two properties of recursively enumerable sets which are undecidable.
5 Is it true that complement of a recursive language is recursive? Justify your answer.
6 When a language is said to be recursive or recursively enumerable?
7 When a language is said to be recursive? Is it true that every regular set is not recursive?
8 When a problem is said to be decidable or undecidable? Give an example of an undecidable.
9 What do you mean by universal Turing Machine?
10.When a problem is said to be undecidable? Give an example of an decidable problem.
11.Show that the union of recursive language is recursive.

UNIT-IV PROPERTIES OF CONTEXTFREE LANGUAGES

1 Define multitape Turing Machine.
2 Explain the Basic Turing Machine model and explain in one move.What are the actions take place in TM?
3 Explain how a Turing Machine can be regarded as a computing device to compute integer functions.
4 Describe the non deterministic Turing Machine model. Is it true the non deterministic Turing Machine model’s are more powerful than the basic Turing Machines? (In the sense of language Acceptance).
5 Explain the multi tape Turing Machine mode. Is it more power than the basic turing machine? Justify your answer.
6 Using Pumping lemma Show that the language L={ anbncn|n>=1} is not a CFL.
7 What is meant by a Turing Machine with two way infinite tape.
8 Define instantaneous description of a Turing Machine.
9 What is the class of language for which the TM has both accepting and rejecting configuration? Can this be called a Context free Language?
10.The binary equivalent of a positive integer is stored in a tape. Write the necessary transition to multiply that integer by 2.
1 What is the role of checking off symbols in a Turing Machine?
2 State Pumping lemma for Context free language.
3 Define a Turing Machine.
4 Mention any two problems which can only be solved by TM.
5 State Pumping lemma and its advantages.
6 What are useless symbols in a grammar.

UNIT-III CONTEXT FREE GRAMMARS AND LANGUAGES

1. Define CFG.2.Find L(G)where G=({S},{0,1},{S->0S1,S->ε},S).
2. Define derivation tree for a CFG(or)Define parse tree.
3. Construct the CFG for generating the language L={anbn/n>=1}.
4. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.for the string aaabbabbba find the left most derivation.
5. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.obtain parse tree for the string aaabbabbba.
6. For the grammar S->aCa,C->aCa/b.Find L(G).
7. Show that id+id*id can be generated by two distinct leftmost derivation in the grammar E->E+E | E*E | (E) | id .
8. For the grammar S->A1B,A->0A | ε, B-> 0B | 1B| ε,give leftmost and rightmost derivations for the string 00101.
9. Find the language generated by the CFG G=({S},{0,1},{S->0/1/ ε, S->0S0/1S1},S).
10 obtain the derivation tree for the grammar G=({S,A},{a,b},P,S) where P consist of S->aAS / a, A->SbA / SS / ba.
11 Consider the alphabet Σ={a,b,(,),+,*, ., ε} .Construct the context free grammar that generates all strings in Σ* that are regular expression over the alphabet {a,b}.
12 Write the CFG to generate the set {am bn cp | m + n=p and p>=1}.
13 Construct a derivation tree for the string 0011000 using the grammar S->A0S |0 | SS , A-> S1A | 10.
14 Give an example for a context free grammar.
15 Let the production of the grammar be S-> 0B | 1A, A-> 0 | 0S | 1AA, B-> 1|1S | 0BB.for the string 0110 find the right most derivation.

CS2303- Theory of Computation

PART-A

1 Define Regular expression. Give an example.
2 What are the operators of RE.
3 Write short notes on precedence of RE operators.Write Regular Expression for the language that have the set of strings over {a,b,c} containing at least one a and at least one b.
4 Write Regular Expression for the language that have the set of all strings of 0’s 5 and 1’s whose 10
the symbol from the right end is 1.
6 Write Regular Expression for the language that has the set of all strings of 0’s and 1’s with at most one pair of consecutive 1’s.
7 Write Regular Expression for the language that have the set of all strings of 0’s
8 and 1’s such that every pair of adjacent 0’s appears before any pair of adjacent 9 1’s.
10 Write Regular Expression for the language that have the set of all strings of 0’s and 1’s whose no of 0’s is divisible by 5.
11 Write Regular Expression for the language that has the set of all strings of 0’s and 1’s not containing 101 as a substring.
12 Write Regular Expression for the language that have theset of all strings of 0’s and 1’s such that no prefix has two more 0’s than 1’s, not two more 1’s than 0’s.
13.Write Regular Expression for the language that have the set of all strings of 0’s and 1’s whose no of 0’s is divisible by 5 and no of 1’s is even.

CS2303- Theory of Computation

PART-A(2-MARKS)
1 List any four ways of theorem proving.
2 Define Alphabets.
3 Write short notes on Strings.
4 What is the need for finite automata?
5 What is a finite automaton? Give two examples.
6 Define DFA.
7 Explain how DFA process strings.
8 Define transition diagram.
9 Define transition table.
10. Define the language of DFA.
11. Construct a finite automata that accepts {0,1}+
12. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings ending in 00.
13. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings with three consecutive 0’s.