Scribd
Upload
16 views2 pages

TOC Assignment Questions3

Theory of computation assignment questions

Uploaded by

shreyashgbusiness
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
16 views2 pages

TOC Assignment Questions3

Theory of computation assignment questions

Uploaded by

shreyashgbusiness
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Srinivasa Educational & Charitable Trust

SAPTHAGIRI COLLEGE OF ENGINEERING


(Affiliated to VTU, Belagavi& Approved by AICTE, New Delhi.)
ISO 9001:2015 & ISO 14001:2015 Certified Institute
Accredited By NAAC with "A" Grade
#14/5, Chikkasandra, Hesaraghatta Main Road, Bengaluru–
560 057

Department of Computer Science and Engineering

Class:5th sem Section: A & B

Sub:Theory of Computation

Assignment Questions-3

1. Define CNF. Convert the following CFG into CNF

S ASB/ɛ, A aAS/a, B SbS/A/bb

2. Simplify the Grammar by removing the Productive and unreachable symbols.

3. Convert the following CFG into CNF

4. Convert the following CFG into CNF

5. What is ambiguity in grammar? Eliminate ambiguity from balanced paranthesis


grammmar.

[Link] the formal definition of Push Down Automata.

7. Illustrate the languages of PDA with an example.


Module 5

1. Write short notes on a. Linear bound Automata

b. Church Turing Thesis

c. Non Deterministic Turing Machine

[Link] Turing Machine. Design Turing Machine for a language

L={0n 1n |n≥1}. Show that the string 0011 is accepted by ID.

3. Explain multiple TM with neat diagram

You might also like