AMCAT Automata and Formal Languages 3

Question 1

A Turing Machine (TM) is more powerful than a Pushdown Automaton (PDA) because:

Accepted Answer

A TM has an infinite tape that can be read and written in both directions, unlike a PDA's stack

Answer

A TM can read input faster than a PDA

Answer

A TM has more states than a PDA

Answer

A TM uses a different alphabet than a PDA

Question 2

Which of the following problems is undecidable?

Accepted Answer

Whether a context-free grammar is ambiguous

Answer

Whether a DFA accepts an empty language

Answer

Whether two DFAs accept the same language

Answer

Whether a regular expression generates a finite language

Question 3

Consider a Moore machine with input alphabet {0, 1} and output alphabet {a, b}. If the machine has 3 states, what is the maximum number of distinct input-output behaviors it can exhibit?

Accepted Answer

18

Answer

6

Answer

8

Answer

72

Question 4

The language L = {a^i b^j c^k | i = j or j = k} is:

Accepted Answer

Context-free but not regular

Answer

Regular

Answer

Context-sensitive but not context-free

Answer

Recursively enumerable but not context-sensitive

Question 5

What is the role of the start symbol in a formal grammar?

Accepted Answer

It is the non-terminal from which all derivations begin

Answer

It represents the input alphabet

Answer

It defines the set of terminal symbols

Answer

It determines whether the grammar is ambiguous

Question 6

Which of the following statements about Deterministic Pushdown Automata (DPDA) is correct?

Accepted Answer

DPDAs are strictly more powerful than DFAs but strictly less powerful than NPDAs

Answer

DPDAs can recognize all context-free languages

Answer

DPDAs and NPDAs recognize the same class of languages

Answer

DPDAs cannot recognize any language that a DFA can recognize