Scribd
Upload
9 views2 pages

Important Toc

The document consists of a series of questions and tasks related to formal languages, automata theory, and Turing machines. Topics include PDA acceptance methods, Turing machine definitions, closure properties of context-free grammars, and the Chomsky hierarchy. Additionally, it covers specific design tasks for Turing machines and grammar conversions, as well as theoretical concepts like decidability and the pumping lemma for context-free languages.

Uploaded by

bindhiyat9889
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
9 views2 pages

Important Toc

The document consists of a series of questions and tasks related to formal languages, automata theory, and Turing machines. Topics include PDA acceptance methods, Turing machine definitions, closure properties of context-free grammars, and the Chomsky hierarchy. Additionally, it covers specific design tasks for Turing machines and grammar conversions, as well as theoretical concepts like decidability and the pumping lemma for context-free languages.

Uploaded by

bindhiyat9889
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/ 2

PART A

1. Differentiate PDA acceptance by empty stack with acceptance by final state..


2. What is an instantaneous description of PDA?.
3. Define Turing machine
4. Mention the closure properties of CFG.
5. List out the different techniques for TM construction.
6. Name the three ways to simplify s context free grammar.
7. State the pumping lemma for CFL.
8. When a language is said to be recursively enumerable?.
9. Give short notes on the Chomsky hierarchy of languages.
10. State the two normal forms and give an example.
11.Write the closure properties of Context free languages.
12.Does push down automata have memory? justify.
13.State the pumping lemma for Context free language.
14.What is universal Turing machine?
15.List out the different techniques for TM construction.
16.Design a TM that accepts the language of odd integers written in binary.
17.Define class P and NP.
18.How could you represent the Turing machine? And write the applications of TM.
19.Distinguish tractable and intractable problem.
20.Give a short note on GNF.

PART B

11.a) (i) Design a Turing machine for palindrome function.


(ii) Convert the grammar with productions into CNF
A→bAB|⅄, B→BAa|⅄
(Or)

L = { 1ⁿ 2ⁿ 3ⁿ : 𝑛 > 1}
11.b) Design a Turing machine M to recognize the language

12.a) (i) Does PCP with two lists x = ( b, bab³, ba ) and y = ( b³, ba, a ) have a
solution?
(ii) Let the input {0,1}. A and B be the lists of three strings each, defined as
List A: wi: 1, 10111, 10
List B: xi: 111, 10, 0. Does this PCP have a solution
(Or)
12.b) Find whether the following languages are recursive or recursively
enumerable
(i) union of two recursive languages.
(ii) union of two recursively enumerable languages.
(iii) L if L and complement of L are recursively enumerable
(iv) if L is recursive then L is RE

13 a) Find a grammar in CNF equivalent to


S→aAbB, A→aA|a, B→bB|b
(or)
13 a) Design a Turing machine that can compute proper subtraction. That is m-n.
m-n if m>n
m-n = 0 if m<n

(ii) Construct a Turing machine M to accept the language L={0ⁿ 1ⁿ: n>1}.
14 a)(i) Define and explain P and NP problems.

Compute 0011.
(or)
14 b)(i) Prove that if a language is recursive if and only if it and its complement
are both recursively enumerable.
(ii) Explain about undecidability of PCP

PART C

1.a) Convert the grammar S→0S|A; A→1A0|S|𝛜 into PDA that accepts the same
language by empty stack.
(Or)
1.b) Construct an unrestricted PDA equivalent to the grammar given below:
S→aAA
A→aS|bS|a

2 a) (i) Prove that if a language is recursive if and only if it and its complement are
both recursively enumerable.
(ii) Explain about undecidability of PCP

Or

2 b)Find a grammar without useless symbols equivalent to


S→AB|CA
A→a
B→BC|AB
C→aB|b

You might also like