AUTOMATA

FINITE AUTOMATA

                             DFA 

DEFINATION

Deterministic finite acceptor (DFA) and a deterministic finite state machine (DFSM)—is a finite-state machine that accepts and rejects strings of symbols and only produces a unique computation (or run) of the automaton for each input string.  Deterministic refers to the uniqueness of the computation. In search of the simplest models to capture finite-state machines

A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q0, F), consisting of

  • a finite set of states (Q)
  • a finite set of input symbols called the alphabet (Σ)
  • a transition function (δ : Q × Σ → Q)
  • an initial or start state (q0 ∈ Q)
  • a set of accept states (F ⊆ Q)

Let w = a1a2 … an be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r0,r1, …, rn, exists in Q with the following conditions:

  1. r0 = q0
  2. ri+1 = δ(ri, ai+1), for i = 0, …, n−1
  3. rn ∈ F.

In words, the first condition says that the machine starts in the start state q0. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings that M accepts is the language recognized by M and this language is denoted by L(M).

A deterministic finite automaton without accept states and without a starting state is known as a transition system or semi automaton.

                             NFA

A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA.

Using the subset construction algorithm, each NFA can be translated to an equivalent DFA, i.e. a DFA recognizing the same formal language.  Like DFAs, NFAs only recognize regular languages. Sometimes the term NFA is used in a narrower sense, meaning an automaton that properly violates an above restriction, i.e. that is not a DFA.

Definition 

An NFA is represented formally by a 5-tuple, (Q, Σ, Δ, q0, F), consisting of

  • a finite set of states Q
  • a finite set of input symbols Σ
  • a transition function Δ : Q × Σ → P(Q).
  • an initial (or start) state q0 ∈ Q
  • a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q. Let w = a1a2 … an be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of states, r0,r1, …, rn, exists in Q with the following conditions:

  1. r0 = q0
  2. ri+1 ∈ Δ(ri, ai+1), for i = 0, …, n−1
  3. rn ∈ F.

In words, the first condition says that the machine starts in the start state q0. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function Δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. In order for w being accepted by M it is not required that every state sequence ends in an accepting state, it is sufficient if one does. Otherwise, i.e. if it is impossible at all to get from q0 to a state from F by following w, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

We can also define L(M) in terms of Δ*: Q × Σ* → P(Q) such that:

  1. Δ*(r, ε)= {r} where ε is the empty string, and
  2. If x ∈ Σ*, a ∈ Σ, and Δ*(r, x)={r1, r2,…, rk} then Δ*(r, xa)= Δ(r1, a)∪…∪Δ(rk, a).

Now L(M) = {w | Δ*(q0, w) ∩ F ≠ ∅}.

Pumping lemma

In the theory of formal languages, the pumping lemma may refer to:

  • Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a sub-string that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular
  • Pumping lemma for context-free languages, the fact that all sufficiently long strings in such a language have a pair of sub-strings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free
  • Pumping lemma for indexed languages
  • Pumping lemma for regular tree languages