Virtual Labs

Acceptance of a string by Pushdown Automaton

Which type of language is recognized by a Pushdown Automaton (PDA)?

a: Regular Explanation

Explanation

b: Context-Free Explanation

Explanation

c: Context-Sensitive Explanation

Explanation

d: Unrestricted Explanation

Explanation

Which data structure is used by a PDA to store additional information?

a: Queue Explanation

Explanation

b: Stack Explanation

Explanation

c: Linked List Explanation

Explanation

d: Array Explanation

Explanation

A PDA accepts a string if:

a: It reaches a final state with non-empty stack Explanation

Explanation

b: It consumes the entire input and reaches a final state and/or has an empty stack Explanation

Explanation

c: It has at least one transition defined for every state Explanation

Explanation

d: The stack contains only the initial symbol Explanation

Explanation

In a PDA transition δ(q, a, X) = (p, α), what does each component represent?

a: q is next state, a is stack symbol, X is input, p is current state, α is new input Explanation

Explanation

b: q is current state, a is input symbol, X is top of stack, p is next state, α is stack replacement Explanation

Explanation

c: q is initial state, a is final symbol, X is empty stack, p is accepting state, α is input string Explanation

Explanation

d: q is stack top, a is next state, X is current state, p is input symbol, α is output Explanation

Explanation

What is the difference between a DFA and a PDA?

a: A PDA uses a stack, while a DFA does not Explanation

Explanation

b: A DFA recognizes context-free languages, while a PDA recognizes regular languages Explanation

Explanation

c: A PDA can only recognize finite languages Explanation

Explanation

d: A DFA can use a stack, while a PDA cannot Explanation

Explanation

What is an epsilon (ε) transition in a PDA?

a: A transition that erases the entire stack Explanation

Explanation

b: A transition that occurs without reading any input symbol Explanation

Explanation

c: A transition that only works when the stack is empty Explanation

Explanation

d: A transition that rejects the input string Explanation

Explanation

Which of the following languages can be recognized by a PDA?

a: L = { a^n b^n c^n | n ≥ 0 } Explanation

Explanation

b: L = { a^n b^n | n ≥ 0 } Explanation

Explanation

c: L = { ww | w ∈ {a,b}* } Explanation

Explanation

d: All regular languages only Explanation

Explanation

Which of the following symbols is commonly used to represent the empty stack in PDA computations?

a: ε (epsilon) Explanation

Explanation

b: Z0 Explanation

Explanation

c: # Explanation

Explanation

d: λ (lambda) Explanation

Explanation

Can a PDFA accept palindromes?

a: yes Explanation

Explanation

b: no Explanation

Explanation

Does the computation power increase by adding another stack?

a: yes Explanation

Explanation

b: no Explanation

Explanation

Do stack symbols and alphabet set need to be the same?

a: yes Explanation

Explanation

b: no Explanation

Explanation