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 is NOT a closure property of regular languages?

a: Union Explanation

Explanation

b: Concatenation Explanation

Explanation

c: Intersection Explanation

Explanation

d: Reverse Explanation

Explanation

Which of the following is an example of a regular language?

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

Explanation

b: L = { w w^R | w ∈ {a, b}* } Explanation

Explanation

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

Explanation

d: L = { a^n b^n c^n | n ≥ 0 } 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

Which of the following operations always result in a regular language when applied to two regular languages?

a: Union and complement Explanation

Explanation

b: Intersection and exponentiation Explanation

Explanation

c: Concatenation and intersection Explanation

Explanation

d: Complement and context-free closure 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