Theory of Computation (AL-601) - Important Questions

Differentiate between Mealy and Moore machines (finite state machines with outputs) with a suitable example.

Define finite automata and list the features of finite automata with an example.

Design a Moore machine to determine the residue of mod 2 of the input treated as a binary string.

What is Moore Machine? How Moore machine can be converted into Mealy Machine? Explain with the help of an example.

Describe how Finite automata can be called a language acceptor?

Explain briefly about the composite machine with an example.

Derive the regular expression corresponding to a given DFA / finite automaton.

Given an NFA with $\epsilon$-transitions, compute $\epsilon$-closure of each state, list strings of length at most 4 accepted, and convert to an equivalent DFA.

Write a short note on any two of: Arden's theorem, Chomsky hierarchy, NPDA, NP-Complete problem.

Design a finite automaton over $\{0,1\}$ accepting strings that start with $1$ and end with $0$.

Minimize the following automata

Determine whether the given NFA accepts the strings abaa and abab.

Construct an equivalent $\epsilon$-NFA for the regular expression $(0+1)^*011$.

Construct an NFA for the language where the second-last symbol is $0$ over $\{0,1\}$ and convert it to an equivalent DFA.

Convert a given $\Lambda$-NFA ($\epsilon$-NFA) to an equivalent NFA.

Design a DFA over $\{0,1\}$ accepting strings whose starting symbol differs from the ending symbol, showing dead state if any.

Define regular language and regular expressions and find the regular expression for the language of all strings that do not end with 01.

State pumping lemma for regular languages. Prove that the language $\{a^n\}$ is not regular. Where $n$ is prime number.

Convert a given context-free grammar (CFG) into Greibach Normal Form (GNF).

Define parse tree and construct a parse tree for the string 'abaabb' from the following given grammar.

$S \rightarrow SS/aSb/\epsilon$

Convert the grammar $\{S \to ABaC|ABa, A \to Aa|a, B \to BaB|b, C \to CC\}$ Chomsky normal form.

Define formally Type 0, Type 1, Type 2 and Type 3 grammar. Show the corresponding automata for each class.

Construct a context-free grammar for $L = \{wcw^R \mid w \in (a+b)^*\}$.

What do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?

Derive representative strings of minimum length 4 from the given context-free grammar.

Differentiate between Context-Free Grammar and Context-Sensitive Grammar.

Prove that $L = \{a^n b^n c^n \mid n \ge 1\}$ is not context-free.

Write a context-free grammar for the regular expression $(011+1)^*(01)^*$.

Construct a PDA for the language of even-length palindromes $L = \{ WW^R \mid W \in \{a,b\}^* \}$ over $\{a,b\}$.

Show that the language $L=\{0^n1^n \mid n \ge 1\}$ is a deterministic context-free language.

Define pushdown automata and explain its model with a neat sketch.

Convert the following grammar into PDA which accepts the same language by empty stack.

$S \rightarrow 0S1/A$

$A \rightarrow 1A0/S/\epsilon$

Construct a PDA accepting by empty stack for $a^nb^nc^md^m$ ($n,m\ge 1$) and $a^3b^n$ ($n\ge 0$).

Construct a PDA accepting by empty stack for $a^nb^mc^n$ ($n,m\ge 1$) and $a^nb^{3n}$ ($n\ge 0$).

Construct a PDA for the language $wcw^R$ where $w$ is a string over $\{0,1\}$.

Define a deterministic PDA and explain how a DPDA differs from a non-deterministic PDA.

Design a PDA to accept the language $\{a^nb^ma^n \mid m,n \ge 1\}$.

What is PDA? Explain instantaneous description of PDA.

Design a Turing Machine that accepts the language $a^n b^n$ (or $1^n 0^n$) where $n \ge 1$.

Design a Turing Machine over $\{0,1\}$ for the language of strings that are multiples of 3.

Find whether the post correspondence problem $P = \{(ba, bab), (abb, bb), (bab, abb)\}$ has a match? Explain in detail.

Write short note on (any three):

Write a short note (any three):

Design a Turing Machine which computes the multiplication of two numbers.

What is a Turing machine? Give its specification and explain it.

Write short notes on NP Hard, Petri Net Model, Halting problem of Turing machine, and 2-way DFA.

Explain P class problems in detail.