CSIT-503 (A) - Theory of Computation

Design an NFA for the language L = { w | w contains substring 101 }.

Compute the Regular Expression for the DFA as shown below alt=''

Find a regular grammar that generates the language on {a, b} consisting of all strings with exactly one a's and no more than two b's.

State and prove Arden's Theorem. Use it to find the regular expression for a Finite Automaton where the transition system involves multiple state equations.

Obtain a grammar in Chomsky Normal Form (CNF) equivalent to the grammar G with productions P given below: S \to aAbB A \to aA | a B \to bb | b

Obtain a CFG that generates the language $L = \{a^i b^j c^k \\mid i, j, k \\ge 0 \\text{ and either } i=j \\text{ or } j=k \}$. Is the grammar you have generated ambiguous?

Construct a PDA accepting $\{a^n b^n a^m \\mid m, n \\ge 1\}$ by final state.

Define a deterministic PDA. How a DPDA differ from a non- deterministic PDA?

Construct Turing Machine (TM) to accept the language $L = \{0^{2n} 1^n 2^{2n} \\mid n \\ge 0\}$ over the alphabet, $\\Sigma = \{0, 1, 2\}$.

What is NP-complete and NP-hard problems? Explain with examples.

Determine the DFA that will accept those words from $S = \{a, b\}$ where the number of b's is divisible by three. Sketch the state table diagram of the finite Automaton M also. alt=''

Given grammar G with productions S \to aB | bA A \to aS | bAA B \to bS | aBB For the string aaabbabbba, find a rightmost derivation, leftmost derivation and parse tree alt=''

Determine a NFA accepting {ab, ba} and use it to find a DFA accepting it.

Give Regular expressions for the following on $\\Sigma = \{a, b, c\}$ (a) all strings containing exactly one a (b) all strings containing no more than three a's (c) all strings which contain at least one occurrence of each symbol in $\\Sigma$.

State and prove Greibach normal Form

Turing machine

Difference between a recursive and recursively enumerable languages

Halting problem