Posts

Showing posts from 2011

Turing Machine Question Bank

Turing Machine (TM) Question Bank
Question List - I


Q.1 (a) Do as Directed.


(i)   Give Difference: TM Vs. PDA. 1

(ii)  Define A TM Computing a Function. 1

(iii) Define A TM Enumerating a Language 1

(iv)  Define Configuration / Instantaneous Description (ID) of TM 2
(b) Define Pumping Lemma for CFL. Prove that L = {  ss | s є {a, b}* } is not Context Free. 5 Q.2 (a) Write a Short note on Turing Machine. 5
(b) Write a Short note on Chomsky Hierarchy. 5


Question List - II


Q.1 (a) Do as Directed.


(i)   Give Difference: TM Vs. FA. 1

Pushdown Automata Question Bank

Image
Pushdown Automata (PDA)  Question Bank
Question List - I


Q.1 (a) Do as Directed.


(i) Give Difference:Top-down Approach Vs Bottom-up Approach. 2

(ii) Specify the types of moves in PDA. 2

(iii) Is NPDA and DPDA Equivalent? Give Example. 1
(b) Write a Short note on Pushdown Automaton. 5 Q.2 (a) Obtain the CFG for following PDA. Give the Corresponding Leftmost Derivation for String : bacab 6



Question List - II


Q.1 (a) Do as Directed.


Context Free Grammar Question Bank

Image
Context Free Grammar Question Bank
Question List - I



Q.1 (a) Do as Directed.


(i)   Define CFG. What is Meaning of Context Free? 2

(ii)  List out steps to convert CFG in to CNF 2

(iii) Define Inherently Ambiguous. 1
(b) Find out What Language is Generated by following CFG. 5

(i)  S → aT | bT | Λ.    T → aS | bS.


(ii) S → aA | bC | b.   A → aS | bB.   B → aC | bA | a.  C → aB | bS
Q.2 (a) Define Derivation Tree or Parse Tree. Show that following grammar is Ambiguous and Find out Unambiguous grammar for same. S → aaaaS | aaaaaaaS | Λ. 5
(b) Prove that The Context Free Grammar G1 with Productions S1 → S1 + T | T   T   → T * F | F F   → ( S1 ) | a

NFA Question List

Image
Non-Deterministic Finite Automata Question List
Question List - I



Q.1 (a)
Find out Regular Expression for Given Finite Automaton. 10 Q.2 (a) Give the Recursive Definition of δ* for an NFA.
Using Subset Construction Draw FA for Given. 5
(b) If L subset of Σ* is a Language that is accepted by the NFA – Λ              M=(Q, Σ, q0, A, δ), then there is an NFA M1=(Q1, Σ, q1, A1, δ1) that also accepts L. 5

OR

(b) Define Acceptance by an NFA.
Check Whether the following strings are accepted by NFA or not. (1) abab         (2)  aaabbb 5


Question List - II



Q.1 (a) Do as Directed.


(i)   Explain Relationship between DFA and NFA.