Unit - 1

Formal Language Theory and Finite Automata

1.1 Finite Automata (FA): An informal picture of FA

A simple language recognition device is a deterministic finite state automaton (DFA). It can be viewed as a machine that works to provide information about strings provided in input or as a mathematical specification.

Strings are supplied into the device through an input tape divided into squares, each containing a single symbol. The machine's basic component is a black box that is in one of a finite number of internal states at any one time, among which we distinguish a starting state and some final states. Using a moving reading head, this black box, dubbed the finite control, can detect what symbol is typed at any place on the input tape. The reading head is first put on the tape's leftmost square, and the finite control is set to a certain beginning state.

The automaton reads one symbol from the input tape at regular intervals and then enters a new state that is solely dependent on the current state and the symbol just read. Following the reading of an input symbol, the reading head travels one square to the right on the input tape, reading the symbol on the next tape square on the next step.

The initial state is Q0, the first symbol to be read is a, and the machine is set up so that when an is read in state Q0, it moves to state Q1.

This procedure is repeated over and over. The reading head eventually reaches the end of the input string. The automaton then indicates whether it approves or disapproves of what it has read by the state it is in at the end: if it ends up in one of the final states, the input string is accepted. The collection of strings that the machine accepts is the language it understands.

Key takeaway

1. A simple language recognition device is a deterministic finite state automaton (DFA).
2. It can be viewed as a machine that works to provide information about strings provided in input or as a mathematical specification.

1.2 Finite State Machine (FSM)

A finite state machine (also known as a finite state automaton) is a computational model that can be implemented in hardware or software to emulate sequential logic and some computer programs. Regular languages are generated via finite state automata. In various domains, such as mathematics, artificial intelligence, gaming, and linguistics, finite state machines can be used to model difficulties.

To recognize patterns, a finite state machine is utilized. The input to a finite automata machine is a string of symbols, and the state of the machine is changed correspondingly. When a desired symbol is found in the input, the transition occurs.

The automata can either migrate to the next state or stay in the current state while transitioning. FA can be in one of two states: accept or reject. The automata will accept when the input string has been correctly digested and the automata has reached its final state.

Finite state machines (FSMs) are divided into two types: deterministic finite state machines (also known as deterministic finite automata) and non-deterministic finite state machines (also known as non-deterministic finite automata). State machines are graphically depicted in a variety of ways, but the concepts behind them are all based on the same computational logic.

Regular languages are recognized or accepted by deterministic finite automata by definition, and a language is regular if it is accepted by a deterministic finite automaton. Languages made up of binary strings that follow a specific pattern are typically used to teach FSMs.

Binary strings can be used to create both regular and non-regular languages. The language of all strings with a 0 as the initial character is an example of a binary string language. Strings like 001, 010, 0, and 01111 (among many others) are valid in this language, however strings like 111, 10000, 1, and 11001100 (among many others) are not.

A finite automata consists of

Q: finite set of states

∑: finite set of input symbol

q0: initial state

F: final state

δ: Transition function

Transition function can be defined as

δ: Q x ∑ →Q 

Finite automata can be characterized into following:

1. DFA (finite automata)
2. NDFA (non deterministic finite automata)

Key takeaway

1. A finite state machine (also known as a finite state automaton) is a computational model that can be implemented in hardware or software to emulate sequential logic and some computer programs.
2. Finite state machines (FSMs) are divided into two types: deterministic finite state machines (also known as deterministic finite automata) and non-deterministic finite state machines (also known as non-deterministic finite automata).

1.3 Language accepted by FA

We can now define the notion of acceptance of a string, and thus acceptance of a language, in terms of a DFA.

If ˆδ (q0, x) ∈ F, a string x is said to be accepted by a DFA A = (Q, Σ, δ, q0, F). That is, the DFA will achieve a final state if the string x ∈ Σ ∗ is applied in the initial state.

The language accepted by A is defined as the set of all strings accepted by the DFA A and is denoted by L (A). That is to say,

L (A) = {x ∈ Σ* | ˆδ (q0, x) ∈ F}

Example:

Take into account the following DFA:

The string ab is the only way to get from the beginning state q0 to the final state q2, and abb is the only way to get to another final state q3. As a result, the DFA's approved language is

{ab, abb}.

Example: Let us recollect the DFA's transition diagram, as given below.

1. It’s important to remember that if the input contains aa, the DFA will take us from the starting state p to the final state r. Due to the fact that r is also a trap state, we will remain at r on any future input.

2. If there is no aa in the input, we will shuffle between p and q but never reach the ultimate state r.

As a result, the DFA accepts the set of all strings over a, b that have aa as a substring, i.e.

{xaay | x, y ∈ {a, b} *}.

1.4 Definition of Regular Language

A regular language is one that may be stated using regular expressions, finite automata, or state machines, both deterministic and non-deterministic. A language is a collection of strings made up of characters or symbols from a specific alphabet. The set of all strings is subdivided into regular languages.

Regular languages are one of the first ideas taught in computability courses, and they are utilized in parsing and developing programming languages. These are useful for assisting computer scientists in seeing patterns in data and grouping specific computational problems together so that they can solve the problems in a similar way. In computability theory, regular languages are a hot topic.

Regular languages are recognized or accepted by deterministic finite automata by definition, and a language is regular if it is accepted by a deterministic finite automaton. Languages made up of binary strings that follow a specific pattern are typically used to teach FSMs.

Regular languages and finite automata can be used to simulate computations that require very little memory. A finite automaton, for example, can create a regular language to describe whether a light switch is on or off, but it can't keep track of how many times the light has been turned on or off.

Fig: Example

The machine above can tell what state it is in right now, on or off, but it doesn't know how many times the switch has been flipped on or off to get there.

Key takeaway

1. A regular language is one that may be stated using regular expressions, finite automata, or state machines, both deterministic and non-deterministic.
2. A language is a collection of strings made up of characters or symbols from a specific alphabet.
3. The set of all strings is subdivided into regular languages.

1.5 FA without output: Deterministic and Nondeterministic FA (DFA and NFA)

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 

Graphical Representation of DFA

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

Q = {q0, q1, q2} 

∑ = {0,1} 

q0 = {q0} 

F = {q2} 

Solution:

Transition Diagram:

Transition Table:

Non-Deterministic FA

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.6 Epsilon- NFA and inter-conversion

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 a 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 automata 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 the current state and repeat step 2.

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

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

Transition state table for DFA corresponding to above NFA

DFA State diagram

Equivalence of NFA 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 ε transformations 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.

1. The computer can switch to any combination of states in the NDFA.
2. Epsilon closure for a given state X is a set of states that can only be reached with (null) or ε moves from states X, including state X itself.
3. When the computer is given a single input to a single state, it goes to a single state in DFA.

1.7 Minimization of DFAs

The term "minimization of DFA" refers to the reduction of the number of states in a particular FA. After reducing the FSM, we have an FSM (finite state machine) with redundant states.

To reduce the DFA, we must follow the various steps. The following are some of them:

Step 1: Using any set of DFA transitions, remove those states that are unreachable from the beginning state.

Step 2: For each pair of states, create a transition table.

Step 3: Divide the transition table into two T1 and T2 tables. T1 is made up of all final states, whereas T2 is made up of non-final states.

Step 4: From T1, find related rows so that:

δ (q, a) = p 

δ (r, a) = p 

That is, discover the two states with the same a and b values and eliminate one of them.

Step 5: Repeat step 3 until no identical rows in the transition table T1 are available.

Step 6: Carry out steps 3 and 4 for table T2 as well.

Step 7: Now join the T1 and T2 tables that have been decreased. The transition table of reduced DFA is the combined transition table.

Example

Solution:

Step 1: Remove the inaccessible states q2 and q4 from the provided DFA.

Step 2: Create a transition table for each of the remaining states.

Step 3: Divide the rows of the transition table into two groups as follows:

1. One set consists of rows that begin in non-final states:

2. A second set has the rows that begin with the final states.

Step 4: Because there are no identical rows in Set 1, Set 1 will be the same as Set 2.

Step 5: Since q3 and q5 transit to the same state on 0 and 1, row 1 and row 2 in set 2 are comparable. So, skip q5 and replace it with q3 in the rest of the questions.

Step 6: Now combine sets 1 and 2 into the following:

It is now the minimized DFA transition table.

Key takeaway

1. The term "minimization of DFA" refers to the reduction of the number of states in a particular FA.
2. After reducing the FSM, we have an FSM (finite state machine) with redundant states.

1.8 FA with output: Moore and Mealy machines -Definition, models, inter-conversion

●      A Finite Automation has a finite number of states and is also called a 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.

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 

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 

Equivalence of moore and merely

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.

Key takeaway -

1. In Finite automata there are a finite number of states, which is used for pattern recognition.
2. FA (finite automata) has a two state - Accept or Reject state
3. In Moore machine the next state is determined by the present state and current input symbol.
4. In Mealy machine the output is represented with each input symbol for each state, separated by /.

References:

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman, “Introduction to Automata Theory Languages and Computation”, Addison-Wesley, ISBN 0-201-44124-1
2. Sanjeev Arora and Boaz Barak, “Computational Complexity: A Modern Approach”,
3. Cambridge University Press, ISBN: 0521424267 97805214242643
4. John Martin, “Introduction to Languages and The Theory of Computation”, 2nd Edition, McGraw-Hill Education, ISBN-13: 978-1-25-900558-9, ISBN-10: 1-25-900558-5
5. J.Carroll & D Long, “Theory of Finite Automata”, Prentice Hall, ISBN 0-13-913708-45