What is a Finite State Machine/Finite Automata?

What is a Power-Set?

Power set of ${2^s}$ of set s is the set of all subsets of S. Examples: ${S_1} = $ {a, b} ${2^{S_1}} = $ {{a}, {b}, {ab}, {0}} ${2^2} = 4$ total elements

${S_2} = $ {a, b, c} ${2^{S_2}} = $ {{0}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}, } ${2^3} = 8$ total elements

What are features of deterministic accepters?

  1. Process an input string, which consist of a sequence of symbols
  2. Make transitions from one state to another state (depending on current state and current input symbol).
  3. Have a finite number of internal states.
  4. Produces some output in a slightly different form.

What is DFA?

Deterministic Finite Accepter (or DFA) is a simple automaton finite state accepter (accepts only a finite set of internal states and no other memory).

For a DFA, the term “deterministic” signifies that the automaton has one and only one option at any time (only one relative path).

DFA is a five-tuple. M = (Q, ${\Sigma}$, ${\sigma}$, ${q_0}$, F) Where:

  1. Q = Finite set of states
  2. ${\Sigma}$ = Finite set of input alphabet symbols
  3. ${\sigma}$ = Transition function mapping: ${Q * {\Sigma} -> Q}$
  4. ${q_0 \in Q}$ = is the initial state.
  5. F ${\subset}$ ${Q}$ = set of final/accept states. Q($F \subset Q$)Has multiple final states.

What is a transition function?

It defines the rules for moving from one state to another state. Ex: If an arrow from a state x to a state y labeled with the input symbol 1, that means that if the automaton is in state x, when it reads a 1, then it moves to state y.

What is a regular language?

It is a language accepted/recognized by a DFA. A language is called a regular language if and only if some nondeterministic finite automaton recognizes it. A language is also considered regular if and only if some regular expression describes it.

NOTE: if an NFA recognizes some language, it can be converted into an equivalent DFA. Consequently, if an NFA recognizes some language, so does some DFA, and hence the langauge is regular.

What is NFA (Nondeterministic Finite Automata)?

Another simple automaton finite state accepter but the only difference is that it has several options/relative paths that it can go to--therefore it has choices to pick which path. In a NFA, there can be zero or more transition on an input. Look at page 48

Think of it as if NFA explores all choices (by search and backtrack method) and makes no decision UNTIL all the options have been analyzed.

  • IMPORTANT: nondeterminism is important for simplifying the solution of many problems.
  • Can think of NFA being a parallel computation where multiple independent “processes” or “threads” can be running concurrently. If NFA splits to follow several choices, it basically corresponds to a process “forking” into several children.

NFA is a five-tuple. M = (Q, ${\sum}$, ${\sigma}$, ${q_0}$, F) Where:

  1. Q = Finite set of states
  2. ${\Sigma}$ = Finite set of input alphabet symbols (finite)
  3. ${\sigma}$ = Transition function mapping: ${Q * {\Sigma} -> Q}$
  4. ${q_0 \in Q}$ = is the initial state.
  5. F ${\subset}$ ${Q}$ = set of final/accept states. Has multiple final/accept states.
  6. ${\sigma}$ maps: Q * (${\Sigma}$ ${\cup}$ {${\lambda}$}) -> ${2^Q}$

2^Q is the powerset.

  • Basically, finite automata is a 5-tuple.

  • If the start state is an accept state, then if the machine reads an empty string, the empty string is accepted.

  • The difference between NFA and DFA in terms of definition is within the transition function.

For DFA, the transition function takes a state and an input symbol and produces the next state; NFA takes a state and an input symbol OR EMPTY STRING and produces the SET OF POSSIBLE NEXT STATES.

Converting NFA to DFA

Let the given NFA be: M = (Q, ${\Sigma}$, ${\sigma}$, ${q_0}$, F) The equivalent DFA be given by: M' = (Q', ${\Sigma}$, ${\sigma}'$, F')

Q' = 2^Q is the powerset of Q and Q = {q0, q1, q2}

  • Look at notes to see the full process. One of the most common methods/processes to construct NFA to DFA is the subset method.