[go: up one dir, main page]
Scribd
Upload
426 views2 pages

Toc Assignment

This document contains assignment questions divided into 5 units on topics related to formal languages and computability theory. Unit 1 covers finite automata minimization and regular expressions. Unit 2 covers context-free grammars. Unit 3 discusses pushdown automata. Unit 4 is about Turing machines. Unit 5 focuses on recursively enumerable languages, complexity classes such as P and NP, and problems like the Post Correspondence Problem and the Traveling Salesman Problem. The assignments involve tasks like constructing automata and grammars, proving theorems, and explaining concepts.

Uploaded by

Vjay Narain
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
426 views2 pages

Toc Assignment

This document contains assignment questions divided into 5 units on topics related to formal languages and computability theory. Unit 1 covers finite automata minimization and regular expressions. Unit 2 covers context-free grammars. Unit 3 discusses pushdown automata. Unit 4 is about Turing machines. Unit 5 focuses on recursively enumerable languages, complexity classes such as P and NP, and problems like the Post Correspondence Problem and the Traveling Salesman Problem. The assignments involve tasks like constructing automata and grammars, proving theorems, and explaining concepts.

Uploaded by

Vjay Narain
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

Unit1 Assignment Questions

1. Minimize the given machine

2. Explain Mealy and moore machine with example.

3. Explain Myhill-Nerode method of minimization?


4. State and prove pumping lemma for regular set?
5. Construct finite automata to the following regular expression

(11+0)*(00+1)*01

Unit2 Assignment Questions

1.Explain rule for Simplification of Context free grammars.


2.Convert the following CFG to GNF
S→AB|0
A→BC|1
B →CD|2
C→AD|0
D→1
3.Define
1) Chomsky Normal form
2) Greibach Normal form
4.Change the following grammer in to CNF
S→abSb|a|aAb
A→bS|aAAb
5. Explain Derivation tree,left most derivation and right most derivation.

Unit3 Assignment Questions


1. Construct PDA for the following set:
L={0n1n2n|n>=1}
2. Construct a PDA equivalent to the following grammer

S→aAA

A→aS|bS|a

3. State and prove pumping lemma for CFG.

4. Difference between deterministic PDA and non-deterministic PDA with example.

5.What are the steps for Converting CFG to PDA?

Unit4 Assignment Questions

1. Define Turning Machine?Explain Turning thesis briefly.


2.Explain how turing machine can be used as generating device?
3. Construct turing machine for accepting L-
L={anbn|n>=0}
4.Types of turing machine?
5. Design a turing machine to recognize all strings consisting of even number of 1’s.

Unit5. Assignment Questions

1. Explain Recursively Enumerable languages.


2.Explain the post correspondence problem.
3. What do you understand by P, NP, NP complete and NP hard problems.
4.Explain traveling sales man problem.
5.Discuss satisfy ability problems.Prove that satisfy ability is NP complete.

You might also like