Arnaiz Mod. Prelim Exam-Automata Theory and Formal Languages

Which of the following is not a type of automaton?

• DFA

• NFA

• PDA

• SQL

A DFA can be simulated by:

• NFA

• PDA

• CFG

• Turing Machine

Which class of languages does DFA accept?

• Regular

• Context-Free

• Recursive

• Recursively Enumerable

In DFA, for each state and input symbol, there is:

• Zero transition

• At most one transition

• Exactly one transition

• More than one transition

Which of the following is more powerful?

• DFA

• NFA

• Both are equally powerful

• None

A language accepted by a PDA but not by a DFA is called:

• Regular

• Context-Free

• Recursive

• None of the above

A PDA can have how many stacks?

• Zero

• One

• Two

• Any number

A Turing machine can simulate which of the following?

• DFA

• PDA

• Any algorithm

• All of the above

The set of all languages accepted by Turing machines is:

• Regular

• Context-Free

• Recursive

• Recursively Enumerable

A context-free grammar is a 4-tuple (V, Σ, R, S) where:

• V is the set of terminals

• Σ is the set of non-terminals

• R is a set of production rules

• S is a terminal