Virtual Labs

Acceptance of a string by Pushdown Automaton

Which of the following best defines a regular language?

a: A language that can be recognized by a pushdown automaton Explanation

Explanation

b: A language that can be recognized by a finite automaton Explanation

Explanation

c: A language that requires a stack for recognition Explanation

Explanation

d: A language that can only be recognized by a Turing machine Explanation

Explanation

Which formalism can be used to describe all regular languages?

a: Context-free grammar Explanation

Explanation

b: Regular expressions Explanation

Explanation

c: Turing machines Explanation

Explanation

d: Lambda calculus Explanation

Explanation

Which of the following statements about memory in finite automata is correct?

a: Finite automata have unlimited memory Explanation

Explanation

b: Finite automata can only remember information through their current state Explanation

Explanation

c: Finite automata can use a stack to store information Explanation

Explanation

d: Finite automata can count arbitrarily large numbers Explanation

Explanation

Why can't a finite automaton recognize the language L = { a^n b^n | n ≥ 0 }?

a: Because it needs to count the number of a's and b's Explanation

Explanation

b: Because it has too many states Explanation

Explanation

c: Because the alphabet is too large Explanation

Explanation

d: Because finite automata can only process strings from left to right Explanation

Explanation

Which of the following statements about regular languages is true?

a: Every regular language can be recognized by a DFA Explanation

Explanation

b: Every regular language requires a PDA for recognition Explanation

Explanation

c: Regular languages can express nested dependencies Explanation

Explanation

d: Regular languages are a superset of context-free languages Explanation

Explanation

The pumping lemma is used to:

a: Prove that a language is regular Explanation

Explanation

b: Convert an NFA to a DFA Explanation

Explanation

c: Show that a language is not regular Explanation

Explanation

d: Generate a regular expression Explanation

Explanation

What type of additional memory structure do pushdown automata use?

a: Queue Explanation

Explanation

b: Stack Explanation

Explanation

c: Array Explanation

Explanation

d: Hash table Explanation

Explanation

If a language is regular, which type of automaton can always recognize it?

a: Pushdown automaton Explanation

Explanation

b: Turing machine Explanation

Explanation

c: Finite automaton Explanation

Explanation

d: Linear bounded automaton Explanation

Explanation