TOC 3B

Which grammar generates {aⁿbⁿcⁿ | n ≥ 1}?

• CFG

• Type 3

• Type 1

• Regular expression

Which of the following is true for deterministic PDA?

• It accepts all CFLs

• Every N-PDA can be converted to D-PDA

• D-PDA languages ⊂ CFLs

• D-PDA = N-PDA

Which production causes left recursion?

• A → aA

• A → Aa

• A → a

• A → ε

The language {aⁿbⁿcᵐ | n, m ≥ 0} is:

• Regular

• Context-free

• Context-sensitive

• Recursive

A PDA accepts by final state if:

• Stack is empty

• Final state is reached

• Both input and stack are empty

• All of the above

In CFG, which form ensures no left recursion?

• Greibach Normal Form

• Chomsky Normal Form

• Leftmost derivation

• Rightmost derivation

Which string is not generated by S → aSb | ab?

• ab

• aabb

• aaabbb

• abab

The PDA transition (q, ε, Z) → (p, AZ) means:

• Push A on top of Z

• Pop Z, push A

• No input read

• All of the above

In a PDA, stack is essential for:

• Backtracking

• Remembering previous states

• Matching nested symbols

• Generating parse trees

Which is ambiguous grammar for aⁿbⁿ?

• S → aSb | ab

• S → SS | aSb | ε

• S → aSb | ε

• S → ab