Theory of Computation — Summer 2024

What are existential quantifiers? If the statement (p) says: “There are some people who work at some place for some time.” How can you write it as a quantified statement?

Explain the strong principle of mathematical induction.

Write the pumping lemma for regular languages and show how it is used to07 show that a language is not regular.

Write all the strings with length less than 4 generate by following grammar: (x + y)∗ ab (a + ab)∗

What do we understand by the two different statements: p → q and P ⇒ Q?04 Are they similar or different?

Show that for any NFA accepting a language Lover 𝛴∗, there is an FA that also07 accepts L.

Show that any regular language can be accepted by a finite automaton.

Explain the difference between ambiguous grammar and unambiguous grammar.

For the given ambiguous grammar, find its equivalent unambiguous grammar: S → ABA04 A→ aA|ꓥ B →bB|ꓥ

Explain all the closure properties of CFG.

What is the dangling else problem?

Describe the language generated by this grammar: S→ aA | bC | b A→ aS | bB B → aC | bA | a C → aB | bS

Explain how every regular expression can be converted to its equivalent07 grammar with an example.

What do we mean by instantaneous description of a PDA?

Write the pumping lemma for the context free languages.

Construct a DPDA to accept the strings with equal number of 0’s and 1’s.

Explain the difference or similarity between language accepted by PDA with empty stack and language accepted by PDA with a state.

Define: Top-Down PDA corresponding to a CFG.

Construct a Nondeterministic PDA for balanced strings of parenthesis.07

Define: “Primitive Recursive Functions”

Explain in short: “Universal Turing Machine.”

Draw a Turing Machine to accept {ss |s ∈ {a,b}∗}

Define: “Bounded Quantifications”

Explain in short, “Multi-tape Turing Machine”

Draw a Turing Machine to accept palindromes over {a,b}*