Deterministic FAs

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

• Q -- finite set of states
• $\Sigma$ -- input alphabet
• $\delta$ -- transition function mapping $Q \times \Sigma \rightarrow q$
• F -- set of final states

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.