IT-503 (B) · Microprocessor and Interfacing/Unsolved PYQ Paper
A THEORY OF COMPUTATION - NOV 2022 Question Paper
-
Unit 27 MarksaCompute the Regular Expression for the DFA as shown below.
-
Unit 17 MarksbDesign DFA's for detecting 1100 Sequence with Overlap over the alphabet $$\Sigma = \left\{0,1\right\}.$$
-
Unit 17 MarksaDesign a NFA that accepts the language over the alphabet, $$\Sigma = \left\{0,1,2\right\}$$ where the decimal equivalent of the language is divisible by 4.
-
Unit 37 MarksbIdentify the language, L generated by the following grammar, G. $$G = \left(\left\{S,A,B\right\},\left\{a,b\right\},P,S\right)$$ where $$P:\\ S \rightarrow AaA \\ A \rightarrow aA \mid a \\ B \rightarrow bBb \mid bb$$
-
Unit 17 MarksaConvert the following NFA to an equivalent DFA.
-
Unit 27 MarksbFind a regular grammar that generates the language on \{a, b\} consisting of all strings with at most one's and more than two b's.
-
Unit 37 MarksaConstruct context free grammars to accept the language $$L(G)=\left\{a^{n}b^{m}c^{m}d^{2n}\mid n\ge 0,\; m\ge 0\right\}$$ over the alphabet, $$\Sigma = \left\{a,b,c,d\right\}.$$
-
Unit 47 MarksbConstruct Non-Deterministic Pushdown Automata (NPDA) to accept the language $$\left\{w\mid w\text{ starts and ends with the same symbol}\right\}$$ over the alphabet, $$\Sigma = \left\{0,1\right\}.$$
-
Unit 57 MarksaConstruct Turing Machine (TM) to accept the language $$L = \left\{0^{n}1^{2n}2^{n}\mid n\ge 0\right\}$$ over the alphabet, $$\Sigma = \left\{0,1,2\right\}.$$
-
Unit 47 MarksbConstruct corresponding CFG for the following NPDA.
-
Unit 47 MarksaGive a Deterministic PDA that accepts $$\left\{a^{n}b^{m}\mid m\ge 2n+2\right\}$$ over the alphabet, $$\Sigma = \left\{a,b\right\}.$$
-
Unit 47 MarksbGive an NPDA that simulates the following (S is start symbol): $$\begin{aligned} S &\rightarrow aABB \mid aAA \\ A &\rightarrow aBB \mid a \\ B &\rightarrow bBB \mid a \end{aligned}$$
-
Unit 57 MarksaProve that the problem of determining whether for a Turing machine M there is some input string for which M halts is undecidable.
-
Unit 57 MarksbProve that the recursive languages are closed under union, intersection, and complement.
-
Unit 34 MarksiGiven the following ambiguous context free grammar $$\begin{aligned} S &\rightarrow Ab \mid aaB \\ A &\rightarrow a \mid Aa \\ B &\rightarrow b \end{aligned}$$ i) Find the string s generated by the grammar that has two leftmost derivations. Show the derivations.
-
Unit 34 Marksiiii) Show the two derivation trees for the string s.
-
Unit 33 Marksiiiiii) Find an equivalent unambiguous context-free grammar.
-
Unit 33 Marksiviv) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above.
Go to where you left off?
Quick Add to Notes
Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.
Create free accountHave an account? Log in
Notes Panel