CSIT-503 (A) - Theory of Computation

Construct a NFA second last symbol is zero over the alphabet (0, 1) than convert in DFA?

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

Write CFG to accept the language defined by, L{a^i b^j c^k i, j, k, >= 0, i = j + k.

Derive Regular Expression from this Finite Automata. alt=''

How $\epsilon$-productions are eliminated from a grammar whose language doesn't have empty string? Remove $\epsilon$-productions from the grammar given below. S $\to$ aA|B|C, A $\to$ aB|$\epsilon$, B $\to$ Aa, C $\to$ aCD, D $\to$ ddd

Construct an equivalent FA for the given regular expression (101)(01 + 11)(10 + 10)

Consider the following productions, S $\to$ aB|bA, A $\to$ aS|bAA|a, B $\to$ bS|aBB|b For the string aabbabbba, find the:

i) Leftmost derivation

ii) Rightmost derivation

iii) Parse Tree

Construct the PDA accepting the language.

i) $L = \{a^n b^{2n} \mid n \ge 1\}$ by empty stack.

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

iii) $L = \{a^n b^{c2m} \mid n \ge 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 ambiguous grammar. Show that the following grammar is ambiguous S $\to$ aSbS | bSaS | $\epsilon$

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

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

Write a short notes (any three):

i) Decidability

ii) Universal Turing Machine

iii) 2 Way DFA

iv) Petranet Model