AUTOMATA MENAGERIE

Venn Diagram

Venn Again

Here's a version of the infamous ``Venn Diagram''. Its rectangles share the ``top edge'' of the page... LANGUAGE GRAMMAR MACHINE CXTY Finite List Enumer. O(n) Reg. Exp S → aT RE=DFA O(n) (ab*)*|(0*1*)* S → b =NFA=RE Context S → aSb NPDA > Poly: Free DPDA > O(n^3) Lin. O(n) DPDA Context aS → bTSa LBA Expon. Sensitive Recursively Undeci- Enumerable aT → b TM dable

DEFINITIONS: TYPES 0-3 (CHOMSKY HIERARCHY)

Erasing Convention (EC). Limit erasing to single S → λ production, with S the start symbol. If that happens, S doesn't appear on RHS of any other productions.

Given that (have to convince self it's OK),

G is Context Sensitive (Type 1): obeys EC, and otherwise for all
α → β, β is at least as long as α.

G is Context Free (Type 2): obeys EC, for all
α → β, α is a single nonterminal.

G is Regular (Type 3): obeys EC and for all
α → β, α is a single nonterminal and β is of form t or tW, t terminal, W non-terminal.

PUSHDOWN AUTOMATON -- CONTEXT FREE LANGUAGES

PUSHDOWN AUTOMATON 2

PUSHDOWN AUTOMATON 3

NPDAs accept context-free languages, Deterministic PDAs accept deterministic context-free languages. Remember palindromes, e.g.
abbabbbbabba is context free
abbabbxbbabba is deterministic context free.

TURING MACHINE

Finite alphabet, Finite number of non-blank cells, finite but unbounded memory. Cell blank or one symbol. FSA reads one cell at any given moment, then either halts or takes these actions:

  1. Print a symbol from alphabet on the cell read (possibly same symbol).
  2. Go to next state (could be same)
  3. Move the Read-Write head one cell left or right.

Describe by set of quintuples
{s, r, p, n, d} for
(current state, current symbol, symbol printed, next state, direction).

In a deterministic TM no two quintuples have same s,r. In nondeterministic, there can be a choice of actions: this models parallelism or precognition but doesn't add power (no new languages accepted).

BUT a deterministic TM may do exponentially more work to simulate the nondet. TM (as with DFA and NDFA) -- related to the P and NP complexity class issue.

TM and Life.

A natural question: what size (say no. of states, symbols) does a TM need? E.g.
are 2 states and three symbols enough?

LINEAR BOUNDED AUTOMATON

For Context Sensitive Grammars.

LBA is a Turing machine with the read-write head restricted to a length that is (a linear function of ) the length of the original input string.

As usual for nondeterministic machines, the NFSA version accepts if there exists a halting sequence given the input.

CONTEXT SENSITIVE GRAMMAR (LBA)

Context |RHS| ≥ |LHS| | V a S → b R S A a ^ | RHA longer than LHS Context Sensitive Grammar productions are non-shrinking only.

If you know that no derivation will ever be longer than the original input, then no intermediate sentential form exceeds that length. Thus you can bound the tape needed for the computation. Hence LBA. A TM's memory needs can shrink and grow unpredictably, hence its power.

Example CONTEXT SENSITIVE GRAMMAR (LBA)

{anbncn | n ≥ 1}

G = (V, T, S, P) with V = {a,b,c,S,B,C}, T = {a,b,c} , S → aSBC, S → aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc

Derivation:

S aSBC aaBCBC aaBBCC aabBCC aabbCC abbcC aabbcc

Not CFG (note multiple-symbol LHSs). Also can't check the length of three different substrings with one stack. Two you can do
(xy an bcd en zw), but not three.

LBA recognizes since non-shrinking productions mean no intermediate sentential form is longer than original input string.

Type 0 Grammar (worse than Context Sensitive). Need Turing machine: has shrinking productions.

Language is empty string λ and all strings with an odd number of 0s ( > 3).
G = (V, T, S, P)
V = {0,A,B,E,F,W,X,Y,Z,S}
T = {0}

P (note shrinking productions) =
{ S → FA, S → FBA, FB → F0EB0, EB → XBY, 0X → 0X, EB → 0, Y0 → 0Y, FX → F0W, YA → Z0A, W0 → 0W, 0Z → Z0, WBZ → EB, F → λ, A → λ}

Derivation: S → FA → λ λ → λ .

S FBA F0EB0A F0XBY0A ... FX0B0YA ... F0W0B0Z0A ... F00WBZ00A F00EB00A F00000A ... 00000 Note X,Y,W,Z march across the 0 string, adding one on each side. Very TM- like.

General Reminder and Warning!

There are many grammars for every language. In particular, one can clearly write a CFG or Turing machine program to recognize RE languages.

Only if it needs a context-sensitive grammar, for instance, is it really a Type 1 language. Nobody seems to talk much about this, but the issue has come up in 173 exams before.