Important RGPV Question, CSIT- 503, (A) Theory of Computation, V Sem, CSIT

Important RGPV Question

CSIT- 503 (A) Theory of Computation

V Sem, CSIT

UNIT 1-Introduction of the theory of computation

Q.1) Compute the Regular Expression for the DFA as shown below

(RGPV Nov 2023)

Q.2) Design DFA’s for detecting 1100 Sequence with Overlap over the alphabet Sigma = {0, 1}

Q.3) Convert the following NFA to an equivalent DFA.

 

Q.4) 

Q.5) 

Q.6) 

Q.7) 

Q.8) 

Q.9) 

Q.10)

UNIT 2-Regular grammars, regular expressions, regular sets

Q.1) Find a regular grammar that generates the language on (a, b) consisting of all strings with at most one a’s and more than two b’s.

(RGPV Nov 2023)

Q.2) 

Q.3) 

Q.4) 

Q.5) 

Q.6) 

Q.7) 

Q.8) 

Q.9) 

Q.10)

 

UNIT 3- Introduction of Context-Free Grammar

Q.1) Construct context free grammars to accept the language L(G)= { an bm cm d2n |n>=0,m>0} over the alphabet,  = {a, b, cd} 

(RGPV Nov 2023)

Q.2) Given the following ambiguous context free grammar

S→Ab| aaB

A→a| Aa

B→b

Q.3) Find the strings generated by the grammar that has two leftmost derivations. Show the derivations.

Q.4) Show the two derivation trees for the string S.

Q.5) Find an equivalent unambiguous context-free grammar.

Q.6) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above.

Q.7) 

Q.8) 

Q.9) 

Q.10)

 

UNIT 4- Introduction of PDA, formal definition

Q.1) Construct Non-Deterministic Pushdown Automata (NPDA) to accept the language {w/w starts and ends with the same symbol} over the alphabet. Σ = {0, 1}

(RGPV Nov 2023)

Q.2) Construct corresponding CFG for the following NPDA.

Q.3) 

Q.4) 

Q.5) 

Q.6) 

Q.7) 

Q.8) 

Q.9) 

Q.10)

 

UNIT 5-Turing machines

Q.1) Construct Turing Machine (TM) to accept the language L= {0 (2n)  | 1n | 2(2n) |n>=0} over the alphabet, Σ = {0, 1, 2}.

(RGPV Nov 2023)

Q.2) Prove that the problem of determining whether for a Turing machine M there is some input string for which M halts is undecidable.

Q.3) Prove that the recursive languages are closed under union, intersection, and complement.

Q.4) 

Q.5) 

Q.6) 

Q.7) 

Q.8) 

Q.9) 

Q.10)

EXTRA QUESTIONS-

Q.1) 

(RGPV Nov 2023)

Q.2) 

Q.3) 

Q.4) 

Q.5) 

Q.6) 

Q.7) 

Q.8) 

Q.9) 

Q.10)

 

Q4 A. tak complete paper nov 2022

— Best of Luck for Exam —