Virtual Labs

Which of the following lists essential components of a Non-Deterministic Pushdown Automaton (NPDA)?

a: States, input alphabet, stack alphabet, transition function, start state, accept states Explanation

Explanation

b: Input alphabet, tape alphabet, transition function, initial state, final state Explanation

Explanation

c: Input alphabet, stack alphabet, transition function, start variable, acceptance state Explanation

Explanation

d: Input alphabet, stack alphabet, transition function, start state, end state Explanation

Explanation

During the conversion from a CFG to an NPDA, how are the CFG productions represented in the automaton?

a: They are discarded. Explanation

Explanation

b: They are converted into states of the NPDA. Explanation

Explanation

c: They are simulated as NPDA transitions (typically ε-moves that replace a nonterminal on the stack with the right-hand side of a production). Explanation

Explanation

d: They are applied directly to the input string. Explanation

Explanation

How does an NPDA typically simulate a derivation step of a CFG (leftmost derivation)?

a: By replacing a nonterminal on the stack with the right-hand side of a production (pushed so the leftmost symbol is on top). Explanation

Explanation

b: By changing states without using the stack. Explanation

Explanation

c: By inserting terminals directly into the input tape. Explanation

Explanation

d: By deleting all variables from the grammar. Explanation

Explanation

What are the two common modes of acceptance for an NPDA?

a: By empty stack and by final state Explanation

Explanation

b: By halting and by looping Explanation

Explanation

c: By epsilon-transition and by state repetition Explanation

Explanation

d: By tape movement and by rewinding Explanation

Explanation

What is the relationship between Context-Free Grammars (CFGs) and Nondeterministic Pushdown Automata (NPDAs)?

a: NPDAs can recognize more languages than CFGs. Explanation

Explanation

b: CFGs can generate more languages than NPDAs. Explanation

Explanation

c: CFGs and NPDAs define the same class of languages (the context-free languages). Explanation

Explanation

d: CFGs and NPDAs are unrelated in computational power. Explanation

Explanation

Which of the following languages can be recognized by an NPDA but not by any finite automaton?

a: All regular languages (e.g., (a+b)*) Explanation

Explanation

b: The language { a^n b^n | n ≥ 0 } Explanation

Explanation

c: Finite languages only Explanation

Explanation

d: All Turing-decidable languages Explanation

Explanation

Conversion of CFG in GNF to NPDA