AMCAT Automata and Formal Languages Flashcards

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

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

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.

Which of the following problems is undecidable?

Answer: Whether a context-free grammar is ambiguous

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.

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?

Answer: 18

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.

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

Answer: Context-free but not regular

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.

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

Answer: It is the non-terminal from which all derivations begin

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.

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

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

DPDAs recognize a proper subset of context-free languages called deterministic context-free languages. They are more powerful than DFAs (which recognize only regular languages) because they have a stack. However, NPDAs can recognize all CFLs, including non-deterministic ones like {ww^R}, which DPDAs cannot.