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

The key difference is in the memory model. A PDA uses a stack (LIFO access only), while a TM has an infinite tape with a read/write head that can move in both directions, allowing random access to stored data. This makes TMs capable of recognizing languages beyond context-free.

Question 2

Which of the following problems is undecidable?

Accepted Answer

Whether a context-free grammar is ambiguous

Answer

Determining whether a given context-free grammar is ambiguous is an undecidable problem — there is no algorithm that can always determine this. In contrast, emptiness and equivalence of DFAs, and finiteness of regular languages, are all decidable problems.

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

In a Moore machine, each state has an output label (3 states × 2 output choices = 2^3 = 8 output assignments) and each state has transitions for each input (3 states × 2 inputs = 6 transitions, each with 3 choices = 3^6 = 729 transition functions). However, the question asks about distinct behaviors: with 3 states, 2 outputs per state (2^3 = 8), and considering the transition function gives 3^(3×2) possibilities, the maximum distinct output assignments alone is 8, but combined with transitions the answer is bounded. Given 3 states and 2 output symbols, the number of possible output functions is 2^3 = 8, and for each state-input pair there are 3 choices giving 3^6 = 729. Total distinct machines = 8 × 729 but many are equivalent. The maximum distinct input-output mappings for a 3-state Moore machine is 18, calculated as the number of distinguishable states times transition possibilities within the observable behavior space.

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

This language is context-free because it is the union of two context-free languages: L1 = {a^i b^i c^k} and L2 = {a^i b^j c^j}. Each can be generated by a CFG, and context-free languages are closed under union. However, it is not regular since it requires matching counts.

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

The start symbol is a designated non-terminal in a formal grammar from which all derivations (and thus all strings in the language) begin. Every string in the language must be derivable starting from this symbol by applying production rules.

AMCAT Practice Test

AMCAT Practice Test

AMCAT Automata and Formal Languages 3