Computing_Principles_Quiz Lab 1 - 2

1. Which of the following models CANNOT recognize regular languages?

• A. Finite Automaton

• B. Turing Machine

• C. Pushdown Automaton

• D. None of the above

In the Chomsky hierarchy, which language type is the most powerful?

• A. Regular

• B. Context-Free

• C. Context-Sensitive

• D. Recursively Enumerable

Which of the following is TRUE about regular expressions?

• A. They can count symbols like a^n b^n.

• B. They can describe all context-free languages.

• C. They are equivalent to finite automata.

• D. They only work for natural languages

Which of the following is NOT a closure property of regular languages?

• A. Union

• B. Intersection

• C. Complement

• D. Counting

Finite automata can count the number of a's and b's in a string?

• True

• False

A pushdown automaton is more powerful than a finite automaton because it has a stack?

• True

• False

Which of the following types of languages can be recognized by a Turing Machine?

• A. Regular Languages

• B. Context-Free Languages

• C. Context-Sensitive Languages

• D. All of the above

Is it possible for a context-free grammar to generate a regular language?

• False

• True

Which of the following is a characteristic of context-sensitive languages?

• C. They can be generated by context-sensitive grammars.

• B. They require a stack for recognition.

• D. They are a subset of regular languages.

• A. They can be recognized by finite automata.

Write a regular expression for strings over {a, b} that start with 'a', end with 'b', and may have any characters in between.