Virtual Labs

What is the primary significance of PDA-CFG equivalence in formal language theory?

a: PDAs are faster than CFGs for string recognition Explanation

Explanation

b: Both models recognize exactly the same class of languages (context-free languages) Explanation

Explanation

c: CFGs are more powerful than PDAs Explanation

Explanation

d: PDAs can only recognize regular languages Explanation

Explanation

In a PDA, what is the role of the stack?

a: To store the input string Explanation

Explanation

b: To provide unlimited memory for computation Explanation

Explanation

c: To maintain context information during computation Explanation

Explanation

d: To replace the need for states Explanation

Explanation

What does a CFG production rule A → α represent?

a: A can be replaced by α during derivation Explanation

Explanation

b: A must appear before α in the final string Explanation

Explanation

c: A and α are equivalent symbols Explanation

Explanation

d: A transforms into α through computation Explanation

Explanation

How does a PDA recognize the language L = {aⁿbⁿ | n ≥ 0}?

a: By counting a's and b's using states Explanation

Explanation

b: By pushing a's onto the stack and popping them for b's Explanation

Explanation

c: By storing the entire string and comparing halves Explanation

Explanation

d: By using regular expression matching Explanation

Explanation

What corresponds to a PDA's epsilon transition in CFG terms?

a: A production rule with empty right-hand side Explanation

Explanation

b: A terminal symbol in the grammar Explanation

Explanation

c: A non-terminal symbol Explanation

Explanation

d: The start symbol of the grammar Explanation

Explanation

In PDA-CFG equivalence, what does the derivation tree height correspond to?

a: The number of input symbols Explanation

Explanation

b: The number of production rules Explanation

Explanation

c: The maximum stack depth during PDA computation Explanation

Explanation

d: The number of accepting states Explanation

Explanation

Why can't deterministic PDAs recognize all context-free languages?

a: They lack sufficient memory Explanation

Explanation

b: They cannot handle ambiguous grammars Explanation

Explanation

c: They process input too slowly Explanation

Explanation

d: Some context-free languages require non-deterministic choice points Explanation

Explanation

In the conversion from CFG to PDA, how are production rules handled?

a: Each rule becomes a single transition Explanation

Explanation

b: Rules are stored in PDA states Explanation

Explanation

c: Right-hand sides are pushed onto the stack when left-hand sides are popped Explanation

Explanation

d: Rules are ignored in the conversion Explanation

Explanation

What computational complexity advantage does the PDA-CFG equivalence provide?

a: It allows choosing the most efficient model for each specific language Explanation

Explanation

b: It proves that context-free languages can be recognized in linear time Explanation

Explanation

c: It eliminates the need for parsing algorithms Explanation

Explanation

d: It reduces space complexity to constant memory Explanation

Explanation

Equivalence of PA and CFG