Unit - 1
Formal Language Theory and Finite Automata
Q1) Explain informal picture of FA?
A1) 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 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.
Q2) Write about finite state machine?
A2) 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:
- DFA (finite automata)
- NDFA (non deterministic finite automata)
Q3) Write about language accepted bt FA?
A3) 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}*}.
Q4) Describe regular expression?
A4) 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.
Q5) Write about DFA?
A5) 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:
- The state is represented by vertices.
- The arc labeled with an input character shows the transitions.
- The initial state is marked with an arrow.
- 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:
Present State | Next State for Input 0 | Next state of Input 1 |
→q0 | q0 | q1 |
q1 | q2 | q1 |
*q2 | q2 | q2 |
Q6) Define Non Deterministic FA?
A6) 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:
- The state is represented by vertices.
- The arc labeled with an input character show the transitions.
- The initial state is marked with an arrow.
- The final state is denoted by the double circle.
Example
- Q = {q0, q1, q2}
- ∑ = {0, 1}
- q0 = {q0}
- F = {q2}
Solution:
Transition Diagram:
Transition table:
Present State | Next State for Input 0 | Next State of Input 1 |
→q0 | q0, q1 | q1 |
q1 | q2 | q0 |
*q2 | q2 | q1,q2 |
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.
Q7) Describe NFA with ε-Transition?
A7) 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
States | 0 | 1 |
A, B, C | B, C | A, B, C |
B, C | C | B, C |
C | C | C |
DFA State diagram
Q8) Explain Equivalence of NFA with and without ε-Transition?
A8) 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:
- Find out all the ε transitions from each state from Q. That will be called as ε-closure{q1} where qi ∈ Q.
- Then δ' transitions can be obtained. The δ' transitions mean a ε-closure on δ moves.
- Repeat Step-2 for each input symbol and each state of given NFA.
- 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.
Q9) What is minimization of DFA?
A9) 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.
Q10) Write any example for minimization of DFA?
A10) Example
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.
State | 0 | 1 |
→q0 | q1 | q3 |
q1 | q0 | q3 |
*q3 | q5 | q5 |
*q5 | q5 | q5 |
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:
State | 0 | 1 |
q0 | q1 | q3 |
q1 | q0 | q3 |
2. A second set has the rows that begin with the final states.
State | 0 | 1 |
q3 | q5 | q5 |
q5 | q5 | q5 |
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.
State | 0 | 1 |
q3 | q3 | q3 |
Step 6: Now combine sets 1 and 2 into the following:
State | 0 | 1 |
→q0 | q1 | q3 |
q1 | q0 | q3 |
*q3 | q3 | q3 |
It is now the minimized DFA transition table.
Q11) Explain Moore Machine?
A11) 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,
- Q: finite set of states
- q0: initial state of machine
- ∑: finite set of input symbols
- O: output alphabet
- δ: transition function where Q × ∑ → Q
- λ: output function where Q → O
Example:
The state diagram for Moore Machine is-
Transition Table for MM (moore machine) is
Current State | Next State(δ) | Output(λ) | |
0 | 1 | ||
q0 | q1 | q2 | 1 |
q1 | q2 | q1 | 1 |
q2 | q2 | q0 | 0 |
Q12) Explain Mealy Machine?
A12) 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
- Q: finite set of states
- q0: initial state of machine
- ∑: finite set of input alphabet
- O: output alphabet
- δ: transition function where Q × ∑ → Q
- λ': 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.
Q13) Write the difference between DFA and NFA?
A13) Difference between DFA and NFA
DFA | NFA |
The transition from a state is to a single Particular next state for each input symbol. Hence it is called deterministic.
| The transition from a state can be to Multiple next states for each input symbol. Hence it is called non-deterministic.
|
Empty string transitions are not seen in DFA. | NDFA permits empty string transitions. |
Requires more space. | Requires less space. |
Backtracking is allowed in DFA | In NDFA, backtracking is not always
Possible.
|
A string is accepted by a DFA, if it transits to a final state.
| A string is accepted by a NDFA, if at least One of all possible transitions ends in a Final state. |
Q14) Convert the given Moore machine into its equivalent Mealy machine?
A14) The transition table of given Moore machine is as follows:
Q | a | b | Output((λ) |
q0 | q1 | q0 | 0 |
q1 | q1 | q2 | 0 |
q2 | q1 | q0 | 1 |
The equivalent Mealy machine can be obtained as follows:
λ' (q0, a) = λ(δ(q0, a))
= λ(q1)
= 0
λ' (q0, b) = λ(δ(q0, b))
= λ(q0)
= 0
The λ for state q1 is as follows:
λ' (q1, a) = λ(δ(q1, a))
= λ(q1)
= 0
λ' (q1, b) = λ(δ(q1, b))
= λ(q2)
= 1
The λ for state q2 is as follows:
λ' (q2, a) = λ(δ(q2, a))
= λ(q1)
= 0
λ' (q2, b) = λ(δ(q2, b))
= λ(q0)
= 0
Hence the transition table for the Mealy machine can be drawn as follows:
The equivalent Mealy machine will be
Q15) Write the difference between moore and mealy machine?
A15) Difference between mealy and moore machine
Mealy Machine | Moore Machine |
Output depends upon both the present state and the present output. | Output depends only upon the present state. |
Generally, it has fewer states than Moore Machine. | Generally, it has more states than Moore Machine. |
The value of the output function is a function of the transitions and the changes, when the input logic on the present state is done. | The value of the output function is a function of the current State and the changes at the clock edges, whenever state changes occur. |
Mealy machines react faster to inputs. They generally react in the same clock cycle. | In Moore machines, more logic is required to decode the outputs resulting in more circuit delays. They generally react one clock cycle later. |