Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA.
S → AS | ε
A → Ab | Bb | ab

List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.

Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q₀, q₁, q₂} , {a, b}, {a, b, B}, δ, q₂, B, F) with input w = ba and δ is defined as follows:
δ(q₀, b) → (q₁, b, R), δ(q₁, a) → (q₂, a, R), δ(q₂, a) → (q₁, a, R), δ(q₂, b) → (q₂, b, L)

Does machine always refer to hardware? Justify. Define positive closure and Kleene closure.

What is undecidable problem? Discuss about Post Correspondence Problem.

Define the language of a grammar. For the grammar S → 0S0 | 1 | ε, show the leftmost derivation for the string 00100 with its parse tree.

Define ε-closure of a state. Differentiate between Moore and Mealy machine.

Represent the following regular grammar to finite automata.
S → aA | aB | ε
A → aA | aS
B → bB | ε

Design the DFA that accepts binary string ending with “00” and show its extended transition function for the string 111000.

Convert the following grammar to CNF.
S → AAB, A → aA | ε, B → ab | a

For the following Turing Machine, test whether the string “( ) ) )” is accepted or rejected and represent it in transition diagram.

Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA.