CS-501 - Theory of Computation

Draw a DFA to accept string of 0's and 1's not ending with the string 01.

Design a DFA to accept string of 0's and 1's when interpreted as binary numbers would be multiple of 3.

Find the context free grammar with no useless symbols equivalent to $S \to AB/CA, B \to BC/AB, A \to a, C \to aB/b$

Derive regular expression from this finite automata. alt=''

What is meant by ambiguous grammar? Test whether the grammar is ambiguous or not $S \to SS/a/b$

Construct an equivalent FA for the given regular expression $(0+1)^* (00+11) (0+1)^*$.

Construct the following CFG grammar

i) $a^m b^n c^n$ where $m, n \ge 1$

ii) Obtain a CFG to generate a integer

Construct the PDA accepting the language:

i) $L = \{ (ab)^n | n >= 1 \}$ by empty stack.

ii) $L = \{ (ww^R) | w \text{ is in } (a+b)^* \}$ by empty stack.

iii) $L = \{ a^n b^n | n >= 1 \}$ by empty stack.

Let G be the grammar given by $S \to AABB/AAA, A \to ABB/a, B \to BBB/A$ construct the PDA that accepts the language generated by this grammar G.

Define the context free grammars in the 4 tuple from $(V, T, P, S)$ for the given languages on $\Sigma = (a, b)$.

i) All strings having atleast two 'a's.

ii) All possible strings not containing triple 'b's.

What is the difference between a recursive and recursively enumerable languages?

What do you mean by saying that the halting problem of TM is undecidable?

Write short notes on : (Any three)

i) Post correspondence problem

ii) Halting problem

iii) Closure property of regular grammar

iv) Turing machine