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 context-free grammar (CFG) consists of which set of components?

a: Terminals, non-terminals, start symbol, and production rules Explanation

Explanation

b: States, transitions, and input symbols Explanation

Explanation

c: Initial state, final state, and stack symbols Explanation

Explanation

d: Alphabet, states, and final states Explanation

Explanation

Which of the following problems can be solved by a context-free grammar (CFG) but not by a DFA?

a: Balanced parentheses Explanation

Explanation

b: String matching Explanation

Explanation

c: Counting even number of zeros Explanation

Explanation

d: Recognizing binary multiples of 3 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

Which of the following is an example of a context-free language?

a: The set of all strings with equal numbers of a's and b's Explanation

Explanation

b: The set of all palindromes over {a, b} Explanation

Explanation

c: The set of binary strings with an even number of zeros Explanation

Explanation

d: The set of all strings that contain 'aa' as a substring Explanation

Explanation

Which of the following is NOT true for context-free grammars?

a: They can generate some non-regular languages Explanation

Explanation

b: They are equivalent in power to PDAs Explanation

Explanation

c: They are closed under union and concatenation Explanation

Explanation

d: They are closed under intersection 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