next up previous contents
Next: Non-deterministic FAs Up: Finite Automata and Regular Previous: Finite Automata and Regular

Deterministic FAs

Deterministic FA - define by 5-tuple $(Q,\Sigma,\delta, q_0, F)$

A string x is accepted if $\delta(q_0,x) = q \in F$. A language L(M) is defined as $L(M) = \{ x \vert \delta(q_o,x) \in F\}$

Critical notion is that for deterministic FA there is a one-to-one mapping between $\Sigma \times Q$ and Q.

Example of deterministic FA: man, wolf, goat problem[*].

Notion that allowed states are determined by transitions.

Another example is the FA which accepts only zeros and ones.

Question regarding infinite vs. finite strings and bearing on FA. Is an infinite string a legal input to FA? Strings are of any length but must be finite.