Unit 1

Basic Concepts and Automata Theory

1.1 Introduction to theory of computation

1.1.1 Automata

●      It is the analysis of abstract machines and the problems of computation that can be solved by these machines.

●      The automaton is called the abstract machine.

●      The primary reason behind the development of the automata theory was the development of methods to explain and analyze the complex behaviour of separate systems.

1.1.2 Computability and Complexity

●      Research issues that the machine can solve, called Decidable problems. (which is the main key in computability)

●      Studying tractable problems solvable with some slowly increasing input size function (such as polynomial) and intractable problems solvable with rapidly growing functions (such as exponential).

●      The key subject of computational complexity is Intractable.

1.1.3 Alphabet

●       Definition − An alphabet is any finite set of symbols.

●       Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are symbols.

1.1.4 Symbol

1.1.5 String

●       Definition − A string is a finite sequence of symbols taken from ∑.

●       Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}

1.1.6 Languages

●       Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.

●       Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then

L1 = {ab, aa, ba, bb} finite language

L2 = {a,aa,aaa,abb,abab}  infinite language

1.2 Deterministic finite automation (DFA)

1.2.1 Definition

In this, for each input symbol, the state to which the machine will move can be determined. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

An automaton can be represented by a 5-tuple (Q, ∑, δ, q 0, F), where −

❖      Q is a finite set of states.

❖      ∑ is a finite set of symbols, called the alphabet of the automaton.

❖      δ is the transition function.

❖      q0 is the initial state from where any input is processed (q 0 ∈ Q).

❖      F is a set of final state/states of Q (F ⊆ Q).

Transition function can be defined as:

δ: Q x ∑→Q 

1.2.2 Representation

A DFA can be represented by digraphs called state diagram. In which:

1. The state is represented by vertices.
2. The arc labeled with an input character shows the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle.

Advantages and disadvantages

❖      DFAs are used to model a Turing machine.

❖      They are used as++ models of computation.

❖      The union/intersection of the languages recognized by two given DFAs.

❖      The complement of the language recognized by a given DFA.

Example

1. Q = {q0, q1, q2} 
2. ∑ = {0,1} 
3. q0 = {q0} 
4. F = {q2} 

Solution:

Transition Diagram:

Transition Table:

1.2.3 Acceptability of a String and Language

After reading the string entirely, a string is accepted by a DFA and the DFA, beginning at the initial state, ends in an accepting state (any of the final states).

A string S is accepted, if any, by the DFA (Q, ∑, δ, q0, F)

δ*(q0, S) ∈ F

The DFA-accepted language L is

{S | S ∈ ∑* and δ*(q0, S) ∈ F}

A DFA (Q, ∑, δ, q0, F) does not accept a string S, if

δ*(q0, S′) ∉ F

The language L not recognized by the DFA/NDFA (Accepted language L complement) is.

{S | S ∈ ∑* and δ*(q0, S) ∉ F}

Example:

Let us take the DFA for consideration. The acceptable strings can be derived from the DFA.

Strings that are approved by the above DFA: {0, 00, 11, 010, 101, ...........}

Strings which were not approved by the above DFA: {1, 011, 111, ........}

1.3 Non-Deterministic Finite Automation (NFA)

In NDFA, the machine can move to any combination of the states. Hence, it is

Called Non-deterministic Automaton.

It has a finite number of states.

❖      Q → Finite non-empty set of states.

❖      ∑ → Finite non-empty set of input symbols.

❖      ∂ → Transitional Function.

❖      q0 → Beginning state.

❖      F → Final State

Transition function can be defined as:

δ: Q x ∑ →2Q

Graphical Representation of NFA

An NFA can be represented by digraphs called state diagram. In which:

1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by the double circle.

Example

1. Q = {q0, q1, q2} 
2. ∑ = {0, 1} 
3. q0 = {q0} 
4. F = {q2}

Solution:

Transition Diagram:

Transition table:

In this figure, we can see that the current state is q0 (input 0), and the next state will be q0, q1 (input 1) so the next state is q1. When the current state is q1 (input 0), the next state will be q2 (input 1), the next state is q0. When the current state is q2 (input 0), the next state is q2 (input 1), the next state will be q1 or q2.

1.4 Equivalence of DFA and NFA

It would seem superficially that deterministic and non-deterministic finite state automata are totally distinct beasts. However, it turns out that they are equivalent. There is a DFA for every language recognized by an NFA that recognizes that language and vice versa.

The NFA to DFA conversion algorithm is relatively simple, even though the resulting DFA is substantially more complicated than the original NFA. I will illustrate this equivalence after the hop and also go through a brief example of converting an NFA to an equivalent DFA.

DFA and NFA Theorem proof -

Let's formally state the theorem we are proving before continuing:

Theorem:

Let the language L ⊆ Σ* be recognized by NFA N = (Σ, Q, q0, F, δ) and assume L.

A DFA D= (Σ, Q ', q'0, F', δ ') exists that also accepts L. (L(N)= L(D)).

We are able to prove by induction that D is equal to N by allowing each state in the DFA D to represent a set of states in the NFA N. Let's define the parameters of D: before we start proofing,

It's worth more explaining, I think δ '. Note that in the set of states Q 'in D, each state is a set of states from Q in N itself. Determine the transition δ (p,a) for each state p in state q in Q 'of D (p is a single state from Q). The union of all δ(q, a) is δ(q,a) .

Now we will demonstrate δ’(q0’, x) =δ’(q0 , x) that for every x  i.e L(D) = L (N)

1.5 NFA with ε-Transition

Epsilon closure for a given state X is a set of states which can be reached from the states X with only (null) or ε moves including the state X itself.

In other words, ε- closure for a state can be obtained by union operation of the ε - closure of the states which can be reached from X with a single ε move in recursive manner.

For the above example ∈ closures are as follows:

∈closure(A): {A, B, C}

∈closure(B): {B, C}

∈closure(C): {C}

Deterministic Finite Automata (DFA):  DFA is a finite automaton where, for all cases, when a single input is given to a single state, the machine goes to a single state, i.e., all the moves of the machine can be uniquely determined by the present state and the present input symbol.

Steps to Convert NFA with ε-move to DFA:

Step 1: Take ∈ closure for the beginning state of NFA as beginning state of DFA.

Step 2: Find the states that can be traversed from the present for each input symbol (union of transition value and their closures for each state of NFA present in current state of DFA).

Step 3: If any new state is found take it as current state and repeat step 2.

Step 4: Do repeat Step 2 and Step 3 until no new state present in DFA transition table.

Step 5: Mark the states of DFA which contains final state of NFA as final states of DFA.

Transition state table for DFA corresponding to above NFA

Fig: DFA State diagram

1.6 Equivalence of NFA’s with and without ε-Transition

NFA can be transformed to NFA with ε without ε and NFA without ε can be converted to DFA with ε. We will use a technique to do this that can extract all the ε transformation from the given NFA. The methods are:

1. Find out all the ε transitions from each state from Q. That will be called as ε-closure{q1} where qi ∈ Q.

2. Then δ' transitions can be obtained. The δ' transitions mean a ε-closure on δ moves.

3. Repeat Step-2 for each input symbol and each state of given NFA.

4. Using the resultant states, the transition table for equivalent NFA without ε can be built.

Eliminating Epsilon Transitions

●      If epsilon transitions can be eliminated from an FA, then construction of an FA from a regular expression can be completed.

●      Epsilon transitions offers a choice: It allows us to stay in a state or move to a new state, regardless of the input symbol.

●      If starting in state s1, state s2 can be reached via a series of epsilon transitions followed by a transition on input symbol x, replacement of the epsilon transitions with a single transition from s1 to s2 on symbol x.

Algorithm for Eliminating Epsilon Transitions

A finite automaton F2 can be built with no epsilon transitions from a finite automaton F1 as follows:

1. The states of F2 are all the states of F1 that have an entering transition labeled by some symbol other than epsilon, plus the start state of F1, which is also the start state of F2.

2. For each state in F1, determine which other states are reachable via epsilon transitions only. If a state of F1 can reach a final state in F1 via epsilon transitions, then the corresponding state is a final state in F2.

For each pair of states i and j in F2, there is a transition from state i to state j on input x if there exists a state k that is reachable from state i via epsilon transitions in F1, and there is a transition in F1 from state k to state j on input x.

1.7 Finite Automata with output

●      A Finite Automation has a finite number of states and is also called as Finite State Machine (FSM).

●      FA (finite automata) is used for recognition patterns.

●       FA have two states, Accept state or Reject state. When the input string is processed successfully, and the automata reaches its final state, then it will accept.

1.4.1 Moore Machine

The Moore machine is a finite state machine in which the current state and the current input symbol define the next state. At a given time, the output symbol depends only on the machine's current state.

Moore machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ) where,

1. Q: finite set of states 
2. q0: initial state of machine 
3. ∑: finite set of input symbols 
4. O: output alphabet 
5. δ: transition function where Q × ∑ → Q 
6. λ: output function where Q → O 

Example:

The state diagram for Moore Machine is-

Transition Table for MM (Moore Machine) is

1.4.2 Mealy Machine

A Mealy Machine is a machine in which the output symbol depends on the machine's current input symbol and current state. The output is expressed in the Mealy machine with each input symbol for each state, separated by /.

The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ') where

1. Q: finite set of states 
2. q0: initial state of machine 
3. ∑: finite set of input alphabet 
4. O: output alphabet 
5. δ: transition function where Q × ∑ → Q 
6. λ': output function where Q × ∑ →O 

1.4.3 Equivalence of Moore and Mealy Machine

Moore and the Mealy machine appear differently from each other.

Designing a Moore machine with a mealy machine is often possible.

Designing a mealy machine with a Moore machine is often possible.

It is possible to transform any Moore machine into a mealy machine.

Moore machine or mealy machine may be used to describe each standard language.

All languages specified by a mealy machine or Moore machine are standard.

Fig: Example of equivalent Moore and mealy machine

A Moore machine M can never be correctly equal to a mealy machine M 'since one greater than that of the mealy machine M' on the same input is the length of the output string of a Moore machine M.

We can, however, overlook the reaction of the Moore machine to input λ and say for all inputs w, Moore machine M and a mealy machine M 'are equivalent if

Where b for its initial state is the output of the Moore machine M

Theorem: If M1= (Q, Σ, Δ, δ, λ, q0) is a Moore machine then there is an M2 equivalent to M1 mealy machine.

Proof: Create a mealy machine M2 as (Q, Σ, Δ, δ, λ’, q0)

λ’ is describe as-

λ’(q,a) = λ(δ (q,a)) For q and input symbols of all states a

Moore machine is on input 1010 output

0 1 2 2 1

Although the output from the mealy machine constructed is

1 2 2 1

By the equivalence state

In the beginning of output of Mealy machine, we can add output of q0 0 of Moore machine.

The machine generated is therefore equivalent to the Moore machine defined.

1.5 Minimization of Finite Automata

It is possible to create infinitely many finite state automata for a given regular language L to accept L. The answer is that there will be a loop in the transition diagram centered on a given DFA M1. To have more states and L(M1) = L(M2) = L, we can create a new DFA M2. And we can create a DFA M3 with even more states and L(M3) = L from DFA M2.

For instance, given a DFA M1, we can create a DFA M2 to have more states and

L(M1) = L(M2) = L.

Example: The following two DFA's are identical to M1 and M2. The collection above the alphabet Σ = {0,1} is accepted by {0n | n>0} both machines.

Machine M2 states q1, q2 and q3 are identical, we can combine these three states in one state as qt in machine M1.

The state qg and qh of the M2 machine are identical, these two states can be combined in one state as qf in the M1 machine.

1.6 Myhill- Nerode Theorem

The Myhill- Nerode language non-regularity test is based on the following theorem, which is in the contrapositive form of the theorem used for the non-regularity test. The Myhill- Nerode theorem is also a consequence:

Theorem: A language L over alphabet is regular if and only if the set of equivalence classes of is finite.

Proof of Theorem -

Suppose L is a regular language and two strings, such as x and y, can be separated with respect to L. Then a string z is given so that xz is in L and yz is not in L (or xz is not in L and yz is in L). This means that the DFA enters various states if x and y are read by a DFA that recognizes L. If there are three strings that are separated with respect to L, then after reading those three strings, the DFA enters three distinct states....

Therefore, with respect to L, if there are infinitely many strings to be separated, then the DFA must have infinitely many states, which it cannot since a DFA must have a finite number of states.

Therefore, if there is an infinite set of strings that can be distinguished pairwise with regard to a language, then the language is not natural.

If, on the other hand, the number of string classes that are pairwise indistinguishable with respect to the L language is finite, the L language is normal.

To prove this, let [x] denote a class of strings that, with respect to L, are indistinguishable from string x. Note that 'indistinguishable from L' is an equivalence relationship over the string set (refer to IL ) and that [x ]'s equivalence classes. We can demonstrate that using these equivalence groups, a DFA that accepts L can be built.

Myhill-Nerode Theorem

Let us state the Myhill-Nerode theorem here. Any terminology first.

For every x, y ∈ *, if x R y, then for every z ∈  *, xR y, then for every z ∈ *, xz R yz, an equivalence relationship R on * is said to be the correct invariant.

If the set of its equivalence classes is finite, an equivalence relation is often said to be of a finite index.

With these words, it is now possible to state the Myhill-Nerode Theorem as follows:

The three sentences that follow are equivalent:

(1)  A language is regular.

(2)  L is the union of some of the equivalence classes of a right invariant equivalent relation of finite index.

(3)  is of finite index.

1.7 Simulation of DFA and NFA

Let N = (QN, Σ, δN, qN0, FN) be an NFA. The equivalent DFA D1 is obtained from the so-called subset construction (also called “power construction”). We define D = (QD, Σ, δD, qD0, FD),

Where

●      The alphabet of D is that of N.

●      The states of D are sets of states of N:

QD = P (QN)

●      The initial state qD0 of D is {qN0}.

●      The final states of D are those sets that contain the final state of N:

FD = {S ∈ P (QN)| S ∩ FN 6= ∅}

●      The transition function of D arises from the transition function of N as follows:

δD (S, a) = Uq∈S δN (q, a)

That is, δD (S, a) is the set of all states of N that are reachable from some state q via a.

References:

1.Introduction to Automata Theory, Languages, and Computation, 2e by John E, Hopcroft, Rajeev Motwani, Jeffery D. Ullman, Pearson Education.

2.Theory of Computer Science (Automata, Languages and Computation), 2e by K. L. P. Mishra and N. Chandrasekharan, PHI

3.Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia.