Formal definitions for different classes of automata;
Part of my notes from ITEC 420 "Computability Theory and Formal Languages" at Radford University, Fall 2015

Finite State Machines

Finite State Machines (FSM) accept regular languages and can be either deterministic or nondeterministic. (Though, we can prove by construction that the two varieties are of equal computing power - an equivalent deterministic FSM can be constructed for any given nondeterministic one.)

Deterministic

Determinstic Finite State Machine (DFSM), a.k.a. Deterministic Finite Automata (DFA)

Formal description

A 5-tuple \(( K, \Sigma, \delta, s, A )\)

• \(K\): Set[State] - states in the machine
• \(\Sigma\): Set[Symbol] - input alphabet
• \(\delta\): Set[((State, Symbol), State)] - transition function, \((K \times \Sigma ) \times K\)
• \(s\): State - the start state, \(s \in K\)
• \(A\): Set[State] - accept states, \(A \subseteq K\)

It is important for the machine to be deterministic that \(\delta\) be a function - for each state, there will be exactly one transition outbound from the state for each symbol in the input alphabet, and every transition will consume one character from the input string.

Computation w/ DFSMs

Configuration

A configuration is an element of \(K \times \Sigma^*\): a 2-tuple (State, String) that represents the current state of the machine and the input left ot be read. The initial configuration is \((s_M, w)\); s_M is the start state of machine M and w is the whole input string.

Yields

One configuration yields another configuration in a single step if there is a transition from the state of the first configuration to the state of the second configuration that consumes the first character of the input string from the first configuration:

\((q_1, c w) \vdash_M (q_2, w) \iff ((q_1, c), q_2) \in \delta\)

Then we can define yields for any number of intermediate steps: \(\vdash_{M^*}\) (It is the transitive, reflexive closure of \(\vdash_M\).) \(C_1 \vdash_{M^*} C_2\) means that M can go from C₁ to C₂ in zero or more steps.

Computation

A computation is a finite sequence of configurations where:

• The first configuration is an initial configuration
• The last configuration is of the form \((q, \epsilon) : q \in K_M\) (the entire input string has been read)
• The _n_th configuration yields the _n+1_th configuration

Accept/reject

• \(M \text{ accepts } w \iff (s, w) \vdash_{M^*} (q, \epsilon) : q \in A_M\)
• \(M \text{ rejects } w \iff (s, w) \vdash_{M^*} (q, \epsilon) : q \notin A_M\)

The computation ends when the entire input has been read; a machine accepts a string if the computation ends in an accept state, and rejects the string otherwise.

The language accepted by M (denoted L(M)) is the set of all strings accepted by M

Non-Deterministic

Nondeterministic Finite State Machine (NDFSM), a.k.a. Nondeterministic Finite Automata (NFA)

Formal description

A 5-tuple \(( K, \Sigma, \Delta, s, A )\)

• \(K\): Set[State] - the states in the machine
• \(\Sigma\): Set[Symbol] - input alphabet
• \(\Delta\): Set[((State, Symbol|Epsilon), State)] - transition relation, \((K \times (\Sigma \cup \{\epsilon\})) \times K\)
• \(s\): State - the start state, \(s \in K\)
• \(A\): Set[State] - accept states. \(A \subseteq K\)

The only difference between the formal definitions of an DFA and NFA is \(\delta\) vs. \(\Delta\). \(\delta\) is a function (it has the property that no element of the domain will map to more than one element in the codomain). \(\Delta\) is a relation (a broader category than a function, because it allows the same element in the domain to map to multiple elements of the co-domain). This is what makes Nondeterministic FSMs nondeterministic - in some configurations there may be an arbitrary choice of which state to proceed to next.

Also note that \(\Delta\) allows for transitions on \(\epsilon\) - transitioning on the empty string. Taking such a transition changes states but consumes no input.

Computation w/ NDFSMs

Configurations, the Yields relation, and Computations are defined like for deterministic FSMs. The difference is in how we exploit nondeterminism and in how we define accept and reject.

Since an NDFSM contains arbitrary transition choices, we can think of simulating an NDFSM by running all possible computations for a particular input string an parallel. Then we say that:

• M accepts if at least one of its computations accepts
• M rejects if none of its computations accepts

Push-Down Automata

Push-Down Automata (PDA) are similar to FSMs, but include a stack structure which can be manipulated as the machine transitions. Like FSMs, they can be either deterministic or non-deterministic. However, unlike FSMs the two types are not equivalent in power. Nondeterministic PDAs can solve problems which cannot be solved by deterministic ones.

We do not distinguish between deterministic and nondeterministic PDAs in formal definition, only by inspection and in the process of computation - a PDA is deterministic if there are no ambiguous choices in any configuration.

Formal description

A 6-tuple \(( K, \Sigma, \Gamma, \Delta, A, s )\)

• \(K\): Set[State] - the states
• \(\Sigma\): Set[Symbol] - input alphabet
• \(\Gamma\): Set[Symbol] - stack alphabet
• \(\Delta\): Set[(State, Input Symbol, Stack Symbol), (State, Stack Symbol)] - transition relation, \((K \times (\Sigma \cup \{\epsilon\}) \times \Gamma^*) \times (K \times \Gamma^*)\)
• \(s\): State - the start state, \(s \in K\)
• \(A\): Set[State] - accept states, \(A \subseteq K\)

That transition relation needs some unpacking. In short, each element is a nested tuple: ((A, B, C), (D, E))

• A: origin state / where the transition begins
• B: symbol which must be at the front of the input string
• C: sequence of symbols which must be at the top of the stack in the given order. Given as a string; when the transition is taken they are popped from the stack.
• D: destination state / where the transition ends
• E: sequence of symbols which will be pushed onto the stack when the transition is taken. Given as a string like C, but sometimes in the reverse of the order in which they are pushed (this lets us read the string from left to right, even though the rightmost symbol is pushed first).

When drawing the machine, the transition arrows between states are labelled "B/C/E" - to take the transition, symbol B must be at the front of the input string and symbol(s) C must be at the top of the stack. When transitioning, C will be popped and E will be pushed.

Note that any of B, C, or E can be \(\epsilon\) - a transition may read nothing from the input string, pop nothing from the stack, or push nothing onto the stack. The equivalent of a fully "empty" \(\epsilon\) transition as in an NDFSM is "\(\epsilon/\epsilon/\epsilon\)".

Computation

TODO (as with FSMs) - distinctive points - stack manipulation, more info in configuration, differences in accepting rejecting, possibility of neither accepting nor rejecting

Turing Machines

TODO: some words here

Like an FSM with an unbounded tape

Formal description

A 6-tuple \(( K, \Sigma, \Gamma, s, H, \delta )\)

• \(K\): Set[State] - the states
• \(\Sigma\): Set[Symbol] - the input alphabet (cannot contain _)
• \(\Gamma\): Set[Symbol] - the tape alphabet, \(\_ \in \Gamma \wedge \Sigma \subset \Gamma\)
• \(s\): State - the start state, \(s \in K\)
• \(H\): Set[State] - halting states, \(H \subseteq K\)
• \(\delta\): Set[((State, Symbol), (State, Symbol, Action))] - transition function, \(((K - H) \times \Gamma) \times (K \times \Gamma \times \{\rightarrow, \leftarrow\})\)

The transition function (ahem - function) looks complicated but breaks down similarly to PDAs. Each member is a nested tuple: ((A, B), (C, D, E))

• A - origin state; cannot be a halting state
• B - symbol on the tape at the machines current position
• C - destination state
• D - symbol to write at the machines current position
• E - direction to move the read head on the tape (right or left)

Each transition in a drawing of a Turing Machine (when not using a macro language) is labelled "B/D/E", e.g. \(b/\_/\leftarrow\) (to take the transition, must read a 'b', write a blank, then move one space to the left).

Computation

TODO ... probably too much to cover here but try to summarize?