UNIT-I

Syllabus
Finite Automata and Regular expressions: Introduction, Finite state machine, DFA and NFA,
NFA with Epsilon transition. Equivalence between NFA with and without Epsilon transitions, NFA
to DFA conversion, minimization of FSM, equivalence between two FSM’s, Finite Automata with
output- Moore and Mealy machines. Regular Expression: Constructing finite Automata for a given
regular expressions, Conversion of Finite Automata to Regular expressions.
Lexical Analysis: Structure of a Compiler, The Role of the Lexical Analyzer, Bootstrapping,
Specification and Recognition of Tokens, Lexical Analyzer Generator-LEX.

1. Finite Automata:
An automaton with a finite number of states is called a Finite Automaton (FA) or Finite
State Machine (FSM).
An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, 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 (q0 ∈ Q).
 F is a set of final state/states of Q (F Q).
Finite Automaton can be classified into two types −
 Deterministic Finite Automaton (DFA)
 Non-deterministic Finite Automaton (NDFA / NFA)
1.1. Deterministic Finite Automaton (DFA)
In DFA, for each input symbol, one can determine the state to which the machine will move. Hence,
it is called Deterministic Automaton. As it has a finite number of states, the machine is called
Deterministic Finite Machine or Deterministic Finite Automaton.
Formal Definition of a DFA
A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
 Q is a finite set of states.
 ∑ is a finite set of symbols called the alphabet.
 δ is the transition function where δ: Q × ∑ → Q
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F Q).
Graphical Representation of a DFA
A DFA is represented by digraphs called state diagram.
 The vertices represent the states.
 The arcs labeled with an input alphabet show the transitions.
 The initial state is denoted by an empty single incoming arc.
 The final state is indicated by double circles.
Example
Let a deterministic finite automaton be as Q = {a, b, c}, ∑ = {0, 1}, q0 = {a}, F = {c}, and
Transition function δ as shown by the following table –
Present State Next State for Input 0 Next State for Input 1
a a b
b c a
c b c
UNIT-I

1.2. Non-deterministic Finite Automaton:

In NDFA, for a particular input symbol, the machine can move to any combination of the
states in the machine. In other words, the exact state to which the machine moves cannot be
determined. Hence, it is called Non-deterministic Automaton. As it has finite number of states, the
machine is called Non-deterministic Finite Machine or Non-deterministic Finite Automaton.
An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
 Q is a finite set of states.
 ∑ is a finite set of symbols calling the alphabets.
 δ is the transition function where δ: Q × ∑ → 2Q
(Here the power set of Q (2Q) has been taken because in case of NDFA, from a state,
transition can occur to any combination of Q states)
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
Graphical Representation of an NDFA: (same as DFA)
An NDFA is represented by digraphs called state diagram.
 The vertices represent the states.
 The arcs labelled with an input alphabet show the transitions.
 The initial state is denoted by an empty single incoming arc.
 The final state is indicated by double circles.
Example
Let a non-deterministic finite automaton be →
 Q = {a, b, c}
 ∑ = {0, 1}
 q0 = {a}
 F = {c}
The transition function δ as shown below −
Present State Next State for Input 0 Next State for Input 1
a a, b b
b c a, c
c b, c c
UNIT-I

DFA vs NDFA
The following table lists the differences between DFA and NDFA.
DFA NDFA
The transition from a state is to a single The transition from a state can be to multiple next
particular next state for each input symbol. states for each input symbol. Hence it is called
Hence it is called deterministic. non-deterministic.
Empty string transitions are not seen in DFA. NDFA permits empty string transitions.
Backtracking is allowed in DFA In NDFA, backtracking is not always possible.
Requires more space. Requires less space.
A string is accepted by a DFA, if it transits to a A string is accepted by a NDFA, if at least one of
final state. all possible transitions ends in a final state.

2. NFA without epsilon to DFA Conversion:

Need? An NFA can have zero, one or more than one move from a given state on a given input
symbol. An NFA can also have NULL moves (moves without input symbol).
On the other hand, DFA has one and only one move from a given state on a given input symbol.
The following procedure converts the NDFA without epsilon to its equivalent DFA −
Algorithm
Let X = (Qx, ∑, δx, q0, Fx) be an NDFA which accepts the language L(X). We have to
design an equivalent DFA Y = (Qy, ∑, δy, q0, Fy) such that L(Y) = L(X).
Input − An NDFA
Output − An equivalent DFA
Step 1 − Create state table from the given NDFA.
Step 2 − Create a blank state table under possible input alphabets for the equivalent DFA.
Step 3 − Mark the start state of the DFA based on the NDFA.
Step 4 − Find out the combination of States {q0, q1,... , qn} for each possible input alphabet.
Step 5 − Each time we generate a new DFA state under the input alphabet columns, we have to apply
step 4 again, otherwise go to step 6.
Step 6 − The states which contain any of the final states of the NDFA are the final states of the
equivalent DFA.
Example
Let us consider the NDFA shown in the figure below.
UNIT-I

The state table of NDFA as shown below:

Using the above algorithm, we find its equivalent DFA. The state table of the DFA is shown in
q δ (q,0) δ (q,1)
a {abcde} {de}
abcde {abcde} {bde}
de {e} {f}
bde {ce} {e}
e {f} {f}
ce {f} {b}
b {c} {e}
c {f} {b}
f {f} {f}
The state diagram of DFA as follows:

Examples:

Example -1
UNIT-I

Example -2

Example -3

Example -4

3. Convert NFA with epsilon to without epsilon (Equivalence between NFA

with and without Epsilon transitions):
The below method is mentioned below stepwise −
 Step 1 − Find out all the ε-transitions from each state from Q. That will be called as ε-
closure(qi) where, qi ∈Q.
 Step 2 − Then, 1 transitions can be obtained. The 1 transitions means an ε-closure on
moves.
 Step 3 − Step 2 is repeated for each input symbol and for each state of given NFA.
 Step 4 − By using the resultant status, the transition table for equivalent NFA without ε can
be built.
UNIT-I

NFA with ε to without ε is as follows −

δ1(q,a) = ∈ - closure (δ (δ∈^(q,∈ ),a)) where, δ^(q,∈ ) = ∈ - closure(q)
Example
Convert the given NFA with epsilon to NFA without epsilon.

Solution
We will first obtain ε-closure of each state i.e., we will find ε-reachable states from the current state.
Hence,
 ε-closure(q0) = {q0,q1,q2}
 ε-closure(q1) = {q1,q2}
 ε-closure(q2) = {q2}
ε-closure(q0) means with null input (no input symbol) we can reach q0, q1, q2.
In a similar manner for q1 and q2 ε-closure are obtained.
Now we will obtain 1 transitions for each state on each input symbol as shown below −
δ'(q0, 0) = ε-closure(δ(δ^(q0, ε),0))
= ε-closure(δ(ε-closure(q0),0))
= ε-closure(δ(q0,q1,q2), 0))
= ε-closure(δ(q0, 0) ∪ δ(q1, 0) U δ(q2, 0) )
= ε-closure(q0 U Φ ∪ Φ)
= ε-closure(q0)
= {q0,q1, q2}

δ'(q0, 1) = ε-closure(δ(δ^(q0, ε),1))

= ε-closure(δ(q0,q1,q2), 1))
= ε-closure(δ(q0, 1) ∪ δ(q1, 1) U δ(q2, 1) )
= ε-closure(Φ ∪q1 U Φ)
= ε-closure(q1)
= {q1, q2}

δ'(q0, 2) = ε-closure(δ(δ^(q0, ε),2))

= ε-closure(δ(q0,q1,q2), 2))
= ε-closure(δ(q0, 2) ∪ δ(q1, 2) U δ(q2, 2) )
= ε-closure(Φ U ΦU q2)
= ε-closure(q2)
= {q2}
δ'(q1, 0) = ε-closure(δ(δ^(q1, ε),0))
= ε-closure(δ(q1,q2), 0))
= ε-closure(δ(q1, 0) U δ(q2, 0) )
= ε-closure(Φ ∪ Φ)
= ε-closure(Φ)
=Φ

δ'(q1,1) = ε-closure(δ(δ^(q1, ε),1))

= ε-closure(δ(q1,q2), 1))
= ε-closure(δ(q1, 1) U δ(q2, 1) )
= ε-closure(q1 ∪ Φ)
UNIT-I

= ε-closure(q1)
= {q1,q2}

δ'(q1, 2) = ε-closure(δ(δ^(q1, ε),2))

= ε-closure(δ(q1,q2), 2))
= ε-closure(δ(q1, 2) U δ(q2, 2) )
= ε-closure(Φ ∪ q2)
= ε-closure(q2)
= {q2}

δ'(q2, 0) = ε-closure(δ(δ^(q2, ε),0))

= ε-closure(δ(q2), 0))
= ε-closure(δ(q2, 0))
= ε-closure(Φ)
=Φ

δ'(q2, 1) = ε-closure(δ(δ^(q2, ε),1))

= ε-closure(δ(q2), 1)
= ε-closure(δ(q2, 1))
= ε-closure(Φ)
=Φ

δ'(q2, 2) = ε-closure(δ(δ^(q2, ε),))

= ε-closure(δ(q2), 2))
= ε-closure(δ(q2, 2))
= ε-closure(q2)
= {q2}
Now, we will summarize all the computed δ' transitions as given below −
δ'(q0,0)={q0,q1,q2}
δ'(q0,1)={q1,q2}
δ'(q0,2)={q2}

δ'(q1,0)= { Φ }
δ'(q1,1)={q1,q2}
δ'(q1,2)={q2}
δ'(q2,0)={ Φ }

δ'(q2,1)={ Φ }
δ'(q2,2)={q2}

The transition table is given below −

States\inputs 0 1 2

q0 {q0,q1,q2} {q1,q2} {q2}

q1 Φ {q1,q2} {q2}

q2 Φ Φ {q2}
UNIT-I

NFA without epsilon

The NFA without epsilon is given below −

Here, q0, q1, q2 are final states because ε-closure(q0), ε-closure(q1) and ε-closure(q2) contain a final
state q2.

4. NFA with epsilon to DFA Conversion:

If any finite automata contain ε (null) move or transaction, then that finite automaton is called NFA
with ∈ moves.
Epsilon (∈) – closure: 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.
Procedure:
Step 1: We will take the ε-closure for the starting state of NFA as a starting state of DFA.
Step 2: Find the states for each input symbol that can be traversed from the present. That means the
union of transition value and their closures for each state of NFA present in the current state of DFA.
Step 3: If we found a new state, take it as current state and repeat step 2.
Step 4: Repeat Step 2 and Step 3 until there is no new state present in the transition table of DFA.
Step 5: Mark the states of DFA as a final state which contains the final state of NFA.
Example 1:
Convert the NFA with ε into its equivalent DFA.

Solution:
Let us obtain ε-closure of each state.
1. ε-closure {q0} = {q0, q1, q2}
2. ε-closure {q1} = {q1}
3. ε-closure {q2} = {q2}
4. ε-closure {q3} = {q3}
5. ε-closure {q4} = {q4}
Now, let ε-closure {q0} = {q0, q1, q2} be state A.
Hence
δ'(A, 0) = ε-closure {δ((q0, q1, q2), 0) }
UNIT-I

= ε-closure {δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0) }

= ε-closure {q3}
= {q3} call it as state B.

δ'(A, 1) = ε-closure {δ((q0, q1, q2), 1) }

= ε-closure {δ((q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1) }
= ε-closure {q3}
= {q3} = B.
The partial DFA will be

Now,
δ'(B, 0) = ε-closure {δ(q3, 0) } = ϕ
δ'(B, 1) = ε-closure {δ(q3, 1) }
= ε-closure {q4}
= {q4} i.e. state C
For state C:
1. δ'(C, 0) = ε-closure {δ(q4, 0) }
2. =ϕ
3. δ'(C, 1) = ε-closure {δ(q4, 1) }
4. =ϕ
The DFA will be,

Examples:
UNIT-I

5. DFA minimization:
DFA minimization stands for converting a given DFA to its equivalent DFA with minimum number
of states. DFA minimization is also called as Optimization of DFA and uses partitioning algorithm.
5.1. Minimization of DFA using sets:
Suppose there is a DFA D < Q, Σ, q0, δ, F > which recognizes a language L. Then the minimized
DFA D < Q’, Σ, q0, δ’, F’ > can be constructed for language L as:
Step 1: We will divide Q (set of states) into two sets. One set will contain all final states and other
set will contain non-final states. This partition is called P0.
Step 2: Initialize k = 1
Step 3: Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, we will take all possible
pair of states. If two states of a set are distinguishable, we will split the sets into different sets in Pk.
Step 4: Stop when Pk = Pk-1 (No change in partition)
Step 5: All states of one set are merged into one. No. of states in minimized DFA will be equal to no.
of sets in Pk.
How to find whether two states in partition Pk are distinguishable?
Two states ( qi, qj ) are distinguishable in partition Pk if for any input symbol a, δ ( qi, a ) and δ ( qj, a
) are in different sets in partition Pk-1.
Example
Consider the following DFA shown in figure.

Step 1. P0 will have two sets of states. One set will contain q1, q2, q4 which are final states of DFA
and another set will contain remaining states. So P0 = { { q1, q2, q4 }, { q0, q3, q5 } }.
Step 2. To calculate P1, we will check whether sets of partition P0 can be partitioned or not:
UNIT-I

i) For set { q1, q2, q4 } :

δ ( q1, 0 ) = δ ( q2, 0 ) = q2 and δ ( q1, 1 ) = δ ( q2, 1 ) = q5, So q1 and q2 are not distinguishable.
Similarly, δ ( q1, 0 ) = δ ( q4, 0 ) = q2 and δ ( q1, 1 ) = δ ( q4, 1 ) = q5, So q1 and q4 are not
distinguishable.
Since, q1 and q2 are not distinguishable and q1 and q4 are also not distinguishable, So q2 and q4 are
not distinguishable. So, { q1, q2, q4 } set will not be partitioned in P1.
ii) For set { q0, q3, q5 } :
δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0
δ ( q0, 1) = q1 and δ( q3, 1 ) = q4
Moves of q0 and q3 on input symbol 0 are q3 and q0 respectively which are in same set in partition
P0. Similarly, moves of q0 and q3 on input symbol 1 are q1 and q4 which are in same set in partition
P0. So, q0 and q3 are not distinguishable.
δ ( q0, 0 ) = q3 and δ ( q5, 0 ) = q5 and δ ( q0, 1 ) = q1 and δ ( q5, 1 ) = q5
Moves of q0 and q5 on input symbol 1 are q1 and q5 respectively which are in different set in
partition P0. So, q0 and q5 are distinguishable. So, set { q0, q3, q5 } will be partitioned into { q0, q3
} and { q5 }. So,
P1 = { { q1, q2, q4 }, { q0, q3}, { q5 } }
To calculate P2, we will check whether sets of partition P1 can be partitioned or not:
iii) For set { q1, q2, q4 } :
δ ( q1, 0 ) = δ ( q2, 0 ) = q2 and δ ( q1, 1 ) = δ ( q2, 1 ) = q5, So q1 and q2 are not distinguishable.
Similarly, δ ( q1, 0 ) = δ ( q4, 0 ) = q2 and δ ( q1, 1 ) = δ ( q4, 1 ) = q5, So q1 and q4 are not
distinguishable.
Since, q1 and q2 are not distinguishable and q1 and q4 are also not distinguishable, So q2 and q4 are
not distinguishable. So, { q1, q2, q4 } set will not be partitioned in P2.
iv) For set { q0, q3 } :
δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0
δ ( q0, 1 ) = q1 and δ ( q3, 1 ) = q4
Moves of q0 and q3 on input symbol 0 are q3 and q0 respectively which are in same set in partition
P1. Similarly, moves of q0 and q3 on input symbol 1 are q1 and q4 which are in same set in partition
P1. So, q0 and q3 are not distinguishable.
v) For set { q5 }:
Since we have only one state in this set, it can’t be further partitioned. So,
P2 = { { q1, q2, q4 }, { q0, q3 }, { q5 } }
Since, P1=P2. So, this is the final partition. Partition P2 means that q1, q2 and q4 states are merged
into one. Similarly, q0 and q3 are merged into one. Minimized DFA corresponding to DFA of Figure
1 is shown in below figure as:

5.2. Minimization of DFA using Myhill-Nerode Theorem:

Minimization of DFA is Required to obtain the minimal and equivalent version of any DFA which
consists of minimum number of states possible. Myhill-Nerode theorem can be used to convert a
DFA to its equivalent DFA with minimum no of states. This method of minimization is also called
Table filling method. There is also another method called Partitioning Method or Equivalence
Method for the minimization of DFA.
Steps for the Minimization of DFA :
UNIT-I

1. Create the pairs of all the states involved in the given DFA.
2. Mark all the pairs (Qa,Qb) such a that Qa is Final state and Qb is Non-Final State.
3. If there is any unmarked pair (Qa,Qb) such a that δ(Qa,x) and δ(Qb,x) is marked, then mark
(Qa,Qb). Here x is a input symbol. Repeat this step until no more marking can be made.
4. Combine all the unmarked pairs and make them a single state in the minimized DFA.

Example
Consider the following DFA,

Following is the transition table for the above DFA.

Minimizing the above DFA using Myhill-Nerode Theorem:

Step-1: Create the pairs of all the states involved in DFA.

Step-2: Mark all the pairs (Qa,Qb) such a that Qa is Final state and Qb is Non-Final State.
UNIT-I

Step-3: If there is any unmarked pair (Qa,Qb) such a that δ(Qa,x) and δ(Qb,x) is marked, then mark
(Qa,Qb). Here x is a input symbol. Repeat this step until no more marking can be made.
 Check for the unmarked pair Q2,Q1
 Check when x=0 : δ(Q2,0) = Q4 and δ(Q1,0) = Q3, check if the pair Q4,Q3 is marked
and no it is not marked.
 Check when x=1 : δ(Q2,1) = Q3 and δ(Q1,1) = Q4, check if the pair Q4,Q3 is marked
and no it is not marked.
 Hence we cannot mark the pair Q2,Q1.
 Check for the unmarked pair Q3,Q0
 Check when x=0 : δ(Q3,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is marked
and no it is not marked.
 Check when x=1 : δ(Q3,1) = Q5 and δ(Q0,1) = Q2, check if the pair Q5,Q2 is marked
and no it is not marked.
 Hence we cannot mark the pair Q3,Q0.
 Check for the unmarked pair Q4,Q0
 Check when x=0 : δ(Q4,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is marked
and no it is not marked.
 Check when x=1 : δ(Q4,1) = Q5 and δ(Q0,1) = Q2, check if the pair Q5,Q2 is marked
and no it is not marked.
 Hence we cannot mark the pair Q4,Q0.
 Check for the unmarked pair Q4,Q3
 Check when x=0 : δ(Q4,0) = Q5 and δ(Q3,0) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Check when x=1 : δ(Q4,1) = Q5 and δ(Q3,1) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Hence we cannot mark the pair Q4,Q3.
 Check for the unmarked pair Q5,Q1
 Check when x=0 : δ(Q5,0) = Q5 and δ(Q1,0) = Q3, check if the pair Q5,Q3 is marked
and yes it is marked.
 Hence we can mark the pair Q5,Q1.

 Check for the unmarked pair Q5,Q2

UNIT-I

 Check when x=0 : δ(Q5,0) = Q5 and δ(Q2,0) = Q4, check if the pair Q5,Q4 is marked
and yes it is marked.
 Hence we can mark the pair Q5,Q2.

 We have checked for all the unmarked pairs but don’t need to stop here we need to continue
this process until no more markings can be made.
 Check for the unmarked pair Q2,Q1
 Check when x=0 : δ(Q2,0) = Q4 and δ(Q1,0) = Q3, check if the pair Q4,Q3 is marked
and no it is not marked.
 Check when x=1 : δ(Q2,1) = Q3 and δ(Q1,1) = Q4, check if the pair Q4,Q3 is marked
and no it is not marked.
 Hence we cannot mark the pair Q2,Q1.
 Check for the unmarked pair Q3,Q0
 Check when x=0 : δ(Q3,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is marked
and yes it is marked.
 Hence we can mark the pair Q3,Q0.


Check for the unmarked pair Q4,Q0

 Check when x=0 : δ(Q4,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is marked
and yes it is marked.
 Hence we cannot mark the pair Q4,Q0.


Check for the unmarked pair Q4,Q3

 Check when x=0 : δ(Q4,0) = Q5 and δ(Q3,0) = Q5, Such pair of state Q5,Q5 don’t
exists.
UNIT-I

 Check when x=1 : δ(Q4,1) = Q5 and δ(Q3,1) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Hence we cannot mark the pair Q4,Q3.
 Now even though we repeat the procedure we cannot mark the pairs Q2,Q1(since Q4,Q3 is
not marked) and Q4,Q3(since Q5,Q5 such pair of states does not exists.). Hence we stop here.
Step-4: Combine all the unmarked pairs and make them as a single state in the minimized DFA.
 The unmarked Pairs are Q2,Q1 and Q4,Q3 hence we combine them.
Following is the Minimized DFA with Q1Q2 and Q3Q4 as the combined states.

 Q0 remains as our starting state.

 Q1 and Q2 were our final states so even we combine them they will remain as the combined
final state.
 Q5 is the another final state we have.
 If we check the original Transition Table
 δ(Q0,0) was Q1 and δ(Q1,1) was Q2. As the states are combined, the transition of Q0
on both the inputs 0 and 1 will be to the state Q1Q2.
 δ(Q1,0) was Q3, δ(Q1,1) was Q4 and δ(Q2,0) was Q4, δ(Q1,1) was Q3. As the states
are combined, the transition of Q1Q2 on both the inputs 0 and 1 will be to the state
Q3Q4.
 δ(Q3,0) was Q5, δ(Q3,1) was Q5 and δ(Q4,0) was Q5, δ(Q4,1) was Q5. As the states
are combined, the transition of Q3Q4 on both the inputs 0 and 1 will be to the state
Q5.
 δ(Q5,0) was Q5 and δ(Q5,1) was Q5. Hence the transition of state Q5 on both the
inputs will be to the state Q5 itself.
Transition table for Minimized DFA

6. Equivalence between two Finite State Machines:

An Automaton is a machine that has a finite number of states. Any Two Automaton is said to be
equivalent if both accept exactly the same set of input strings.
Two Automaton are equivalent if they satisfy the following conditions:
1. The initial and final states of both the automatons must be same.
2. Every pair of states chosen is from a different automaton only.
3. While combining the states with the input alphabets, the pair results must be either both final states
or intermediate states (i.e both should lie either in the final state or in the non-final state).
4. If the resultant pair has different types of states, then it will be non-equivalent. (i.e. One lies in the
final state and the other lies in the intermediate state).
UNIT-I

Example 1 – Consider Two Different Automaton shown below in Figure 1.

Solution:
Step 1 – Since the initial and final states of both the automaton are the same, so it verifies.
Step 2 – Check for each state by making a table of states with respect to input alphabets.

Here, F.S represents -> Final State. I.S represents -> Intermediate State (Non-Final State) .
Step 3 – For every pair of states, the resultant states lie either in F.S or in I.S as a combination.
Conclusion – Both the Automaton are equivalent.
Note: If the resultant pair of states has a different combination of states(i.e. either (F.S, I.S) or (I.S,
F.S), then both the automata are said to be non-equivalent.

Example 2: Consider Two Different Automaton shown below in Figure 2.

UNIT-I

Solution:
Step 1 – Since the initial and final states of both the automaton are the same so it verifies.
Step 2 – Check for each state by making a table of states with respect to input alphabets.

Here, F.S represents -> Final State. I.S represents -> Intermediate State (Non-Final State).
Step 3 – For the first pair of states, the resultant states lie in F.S as a combination Step
4 – But for the pair (q2,q5) when operated over input alphabets they lie in different states. (i.e. one in
F.S and the other in I.S).
Conclusion – The Given Automata are not equivalent.

Example 3 – Consider Two Different Automaton shown below in Figure 3.

Solution:
Step 1 – Since the initial and final states of both the automaton are the same so it verifies.
Step 2 – Check for each state by making a table of states with respect to input alphabets.

Here, F.S represents -> Final State. I.S represents -> Intermediate State (Non-Final State).
Step 3 – For the pair (q1,q3), when operated over input alphabets they lie in different states. (i.e. one
in F.S and the other in I.S).
Conclusion – The Given Automata are not equivalent.

Example 4 – Consider Two Different Automaton shown below in Figure 4.

Solution:
Step 1 – Since the initial and final states of both the automaton are the same, so it verifies.
Step 2 – Check for each state by making a table of states with respect to input alphabets.
UNIT-I

Here, F.S represents -> Final State. I.S represents -> Intermediate State (Non-Final State).
Step 3 – For every pair of states, the resultant states lie either in F.S or in I.S as a combination.
Conclusion – Both the Automaton are equivalent.

7. Finite Automat with Output:

The finite automata which we considered earlier have binary output i.e. they accept the string
or do not accept the string. decided on the basis of reachability of the final state by the initial
state.
Now we remove this restriction and consider the model where the outputs can be chosen from
some other alphabet.
six tuple (Q, Σ, Δ, λ, δ, q0):
• Q is a finite set of states
• Σ is the input alphabet
• Δ is the output alphabet
• δ is the transition function Σ x Q  Q.
• λ is the output function mapping and
• q0 is the initial state

7.1. Moore Machine:

Moore machine is a finite state machine in which the next state is decided by the current state and
current input symbol. The output symbol at a given time depends only on the present state of the
machine. 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. Δ: output alphabet
5. δ: transition function where Q × ∑ → Q
6. λ: output function where Q → Δ
Example 1:
The state diagram for Moore Machine is
UNIT-I

Transition table for Moore Machine is:

In the above Moore machine, the output is represented with each input state separated by /. The
output length for a Moore machine is greater than input by 1.
Input: 010
Transition: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2
Output: 1110(1 for q0, 1 for q1, again 1 for q1, 0 for q2)

7.2. Mealy Machine:

A Mealy machine is a machine in which output symbol depends upon the present input symbol
and present state of the machine. In the Mealy machine, the output is represented with each
input symbol for each state separated by /. The Mealy machine can be described by 6 tuples (Q,
q0, ∑, O, δ, λ') where
1. 1. Q: finite set of states
2. q0: initial state of machine
3. ∑: finite set of input symbols
4. Δ: output alphabet
5. δ: transition function where Q × ∑ → Q
6. λ: output function where Q × ∑ → Δ

Example 1:
Design a Mealy machine for a binary input sequence such that if it has a substring 101, the
machine output A, if the input has substring 110, it outputs B otherwise it outputs C.

Solution: For designing such a machine, we will check two conditions, and those are 101 and
110. If we get 101, the output will be A. If we recognize 110, the output will be B. For other
strings the output will be C.
The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Mealy machine
becomes:
UNIT-I

7.3. Moore to Mealy Conversion:

Moore machines can be converted to Mealy machines with a few simple steps. We know that Mealy
machines are faster, so we may want to convert our Moore machine to a Mealy machine.
Conversion techniques
There are two techniques to convert these machines:
1. By transition diagram
2. By transition table
Let's take examples of both of these techniques.
7.3.1. By transition diagram
The steps involved in this method are:
1. To redraw the original states without the output. The starting state remains the same.
2. Draw the transitions as they are on the original machine.
3. Add output to the transitions based on their destination's output symbol in the original
machine.
Example
Let's take a simple Moore machine:

1. We redraw the states without the output:

UNIT-I

2. Draw transitions:

3. Now we add output to the transitions based on the transition's destination:

This is the final Mealy machine.

7.3.2. By transition table
The steps involved in this method are:
1. To rewrite the table, excluding the output column.
2. To add the output to the destination columns adjacent to the destination state. The output will
be according to the output of the destination state in the Moore machine transition table.
Example
Let's take the transition table of the previous example is:
Current State Destination State for 0 Destination State for 1 Output
q0 q0 q1 a
q1 q2 q0 b
q2 q0 q1 a
1. We will rewrite the table above without the output table:
Current State Destination State for 0 Destination State for 1
q0 q0 q1
q1 q2 q0
q2 q0 q1
2. Now, we'll add the output symbols to the destination symbols by looking at the original table:
Current State Destination State and output for 0 Destination State and output for 1
q0 q0, a q1, b
q1 q2, a q0, a
q2 q0, a q1, b
For example, for q0, the destination state for 1 is q1. As a result, we see that the output against q1 in
the original table is b, so the output here will also become b.
This is the final transition table of the Mealy machine.

7.4. Mealy to Moore Conversion:

In Moore machine, the output is associated with every state, and in Mealy machine, the output is
given along the edge with input symbol. To convert Moore machine to Mealy machine, state output
symbols are distributed to input symbol paths. But while converting the Mealy machine to Moore
machine, we will create a separate state for every new output symbol and according to incoming and
outgoing edges are distributed.
The following steps are used for converting Mealy machine to the Moore machine:
Step 1: For each state (Qi), calculate the number of different outputs that are available in the
transition table of the Mealy machine.
Step 2: Copy state Qi, if all the outputs of Qi are the same. Break qi into n states as Qin, if it has n
distinct outputs where n = 0, 1, 2....
Step 3: If the output of initial state is 0, insert a new initial state at the starting which gives 1 output.
UNIT-I CD

Example 1:
Convert the following Mealy machine into equivalent Moore machine.

Solution:
Transition table for above Mealy machine is as follows:

o For state q1, there is only one incident edge with output 0. So, we don't need to split this state
in Moore machine.
o For state q2, there is 2 incident edge with output 0 and 1. So, we will split this state into two
states q20 (state with output 0) and q21(with output 1).
o For state q3, there is 2 incident edge with output 0 and 1. So, we will split this state into two
states q30 (state with output 0) and q31 (state with output 1).
o For state q4, there is only one incident edge with output 0. So, we don't need to split this state
in Moore machine.
Transition table for Moore machine will be:

Transition diagram for Moore machine will be:

Blog: [Link] 22
Example 2:
Convert the following Mealy machine into equivalent Moore machine.

Solution:
Transition table for above Mealy machine is as follows:

The state q1 has only one output. The state q2 and q3 have both output 0 and 1. So we will create two
states for these states. For q2, two states will be q20(with output 0) and q21(with output 1).
Similarly, for q3 two states will be q30(with output 0) and q31(with output 1).
Transition table for Moore machine will be:

Transition diagram for Moore machine will be:

8. Applications of Finite Automata:
Finite Automata have several applications.
1. A Finite Automata is highly useful in designing Lexical Analyzers.
2. A Finite Automata is highly useful in designing text editors.
3. A Finite Automata is highly useful in designing spell checkers.
4. A Finite Automata is highly useful in designing Sequential Circuit design (or) Hardware
Design.
5. String processing.
Example:
Q: To find all occurrences of pattern 1001, construct the DFA for all strings ending in
1001.

9. Converting a regular expression to a NFA - Thompson's Algorithm:

We will use the rules which defined a regular expression as a basis for the construction:
1. The NFA representing the empty string is:

2. If the regular expression is just a character, eg. a, then the corresponding NFA is :

3. The union operator is represented by a choice of transitions from a node; thus a|b can be
represented as:

4. Concatenation simply involves connecting one NFA to the other; eg. ab is:

5. The Kleene closure must allow for taking zero or more instances of the letter from the input;
thus a* looks like:

Example:
Find NFA-Ԑ for regular expression (a+bb)*
A) Consider NFA for ‘a’
 Consider NFA for ‘b’

Consider NFA for ‘bb’

Consider NFA for ‘a+bb’

Consider NFA for ‘(a+bb)*’

10. Conversion of Finite Automata (FA) into Regular Expression (RE):

There are two popular methods for converting a DFA to its regular expression −
1. Arden’s Method
2. State elimination method
1. Arden’s Method:
Let P and Q be 2 regular expressions. If P does not contain null string, then the following
equation in R, viz R = Q + RP, Has a unique solution by R = QP* Assumptions –
 The transition diagram should not have €-moves.
 It must have only one initial state.
Using Arden’s Theorem to find Regular Expression of Deterministic Finite automata –
1. For getting the regular expression for the automata we first create equations of the given
form for all the states q1 = q1w11 +q2w21 +…+qnwn1 +€ (q1 is the initial state) q2 =
q1w12 +q2w22 +…+qnwn2 . . . qn = q1w1n +q2w2n +…+qnwnn wij is the regular expression
representing the set of labels of edges from qi to qj Note – For parallel edges there will
be that many expressions for that state in the expression.
2. Then we solve these equations to get the equation for qi in terms of wij and that
expression is the required solution, where qi is a final state.
Example :-

Solution :- Here the initial state is q1 and the final state is q1. The equations for the three states q1,
q2, and q3 are as follows ? q1 = q1a + q3a + € ( € move is because q1 is the initial state) q2 = q1b +
q2b + q3b q3 = q2a Now, we will solve these three equations ? q2 = q1b + q2b + q3b = q1b + q2b +
(q2a)b (Substituting value of q3) = q1b + q2(b + ab) = q1b (b + ab)* (Applying Arden’s Theorem)
q1 = q1a + q3a + € = q1a + q2aa + € (Substituting value of q3) = q1a + q1b(b + ab*)aa + €
(Substituting value of q2) = q1(a + b(b + ab)*aa) + € = € (a+ b(b + ab)*aa)* = (a + b(b + ab)*aa)*
Hence, the regular expression is (a + b(b + ab)*aa)*.
2. State elimination method:
Let’s consider the state elimination method to convert FA to RE.
The rules for state elimination method are as follows −
Rule 1
The initial state of DFA must not have any incoming edge.
If there is any incoming edge to the initial edge, then create a new initial state having no incoming
edge to it.
Rule 2
There must exist only one final state in DFA.
If there exist multiple final states, then convert all the final states into non-final states and create a
new single final state.
Rule 3
The final state of DFA must not have any outgoing edge.
If this exists, then create a new final state having no outgoing edge from it.
Rule 4
Eliminate all intermediate states one by one.
Now, apply these rules to convert the FA to RE easily.
The given FA is as follows −

Step 1
Initial state q1 has an incoming edge so create a new initial state qi.
Step 2
Final state q2 has an outgoing edge. So, create a new final state qf.

Step 3
Start eliminating intermediate states
First eliminate q1
There is a path going from qi to q2 via q1. So, after eliminating q1 we can connect a direct path from
qi to q2 having cost.
εc*a=c*a
There is a loop on q2 using state qi. So, after eliminating q1 we put a direct loop to q2 having cost.
b.c*.a=bc*a
After eliminating q1, the FA looks like following −

Second eliminate q2
There is a direct path from qi to qf so, we can directly eliminate q2 having cost −
C*a(d+bc*a)* ε = c*a(d+bc*a)*
Which is our final regular expression for given finite automata.

11. Introduction to Language Processing System:

We have learnt that any computer system is made of hardware and software. The hardware
understands a language, which humans cannot understand. So we write programs in high-level
language, which is easier for us to understand and remember. These programs are then fed into a
series of tools and OS components to get the desired code that can be used by the machine. This is
known as Language Processing System.
The high-level language is converted into binary language in various phases. A compiler is a
program that converts high-level language to assembly language. Similarly, an assembler is a
program that converts the assembly language to machine-level language.

Let us first understand how a program, using C compiler, is executed on a host machine.
 User writes a program in C language (high-level language).
 The C compiler compiles the program and translates it to assembly program (low-level
language).
 An assembler then translates the assembly program into machine code (object).
 A linker tool is used to link all the parts of the program together for execution (executable
machine code).
 A loader loads all of them into memory and then the program is executed.
Before diving straight into the concepts of compilers, we should understand a few other tools that
work closely with compilers.
 Fig: Language Processing System.
Pre-processor- A pre-processor, generally considered as a part of compiler, is a tool that produces
input for compilers. It deals with macro-processing, file inclusion, language extension, augmentation
etc.
Interpreter– It like a compiler translates high-level language into low-level machine language. The
difference lies in the way they read the source code or input. A compiler reads the whole source code
at once, creates tokens, checks semantics, generates intermediate code, executes the whole program
and may involve many passes. In contrast, an interpreter reads a statement from the input converts it
to an intermediate code, executes it, then takes the next statement in sequence. If an error occurs, an
interpreter stops execution and reports it. Whereas a compiler reads the whole program even if it
encounters several errors.
Assembler- An assembler translates assembly language programs into machine code. The output of
an assembler is called an object file, which contains a combination of machine instructions as well as
the data required to place these instructions in memory.
Linker- Linker is a computer program that links and merges various object files together in order to
make an executable file. All these files might have been compiled by separate assemblers. The major
task of a linker is to search and locate referenced module/routines in a program and to determine the
memory location where these codes will be loaded, making the program instruction to have absolute
references.
Loader- Loader is a part of the operating system and it is responsible for loading executable files
into memory and executes them. It calculates the size of a program (instructions and data) and
creates memory space for it. It initializes various registers to initiate execution.
Compiler -Compiler is a translator, which translates a program written in (HLL / source program)
into an equivalent program in (MLL / target program). As an important part of a compiler is showing
an error /warning messages to the programmer if existing.
Cross-compiler- A compiler that runs on platform (A) and is capable of generating executable code
for platform (B) is called a cross-compiler.
Source-to-source Compiler- A compiler that takes the source code of one programming language
and translates it into the source code of another programming language is called a source-to-source
compiler.

12. Structure of a Compiler:

We basically have two phases of compilers, namely Analysis phase and Synthesis phase.
Analysis phase creates an intermediate representation from the given source code. Synthesis phase
creates an equivalent target program from the intermediate representation.
• We basically have two phases of compilers, namely Analysis phase and Synthesis phase.
Analysis phase creates an intermediate representation from the given source code. Synthesis
phase creates an equivalent target program from the intermediate representation.

Fig: Structure of a compiler

Once again Analysis phase is divided into four phases as:
1. Lexical Analyzer
2. Syntax Analyzer
3. Semantic Analyzer
4. Intermediate Code Generator
Synthesis phase is divided into four phases as:
5. Code optimization
6. Code generator

Fig: structure of a compiler with all phases

Symbol Table – It is a data structure being used and maintained by the compiler, consists all the
identifier’s name along with their types. It helps the compiler to function smoothly by finding the
identifiers quickly.
Lexical Analyzer – It reads the program and converts it into tokens. It converts a stream of lexemes
into a stream of tokens. Tokens are defined by regular expressions which are understood by the
lexical analyzer. It also removes white-spaces and comments.
Syntax Analyzer – It is sometimes called as parser. It constructs the parse tree. It takes all the tokens
one by one and uses Context Free Grammar to construct the parse tree.
Semantic Analyzer – It verifies the parse tree, whether it’s meaningful or not. It furthermore
produces a verified parse tree.
Intermediate Code Generator – It generates intermediate code, which is a form in between source
code and machine code.
Code Optimizer – It transforms the code so that it consumes fewer resources and produces more
speed. Optimisation can be categorized into two types: machine dependent and machine independent.
Target Code Generator – The main purpose of Target Code generator is to write a code that the
machine can understand.
The tasks of the Error Handler are to detect each error, report it to the user, and then make some
recover strategy and implement them to handle error.
Example
13. Role of the Lexical Analysis:
a) Functionality of the Lexical Analysis
To identify the tokens, we need some method of describing the possible tokens that can
appear in the input stream. For this purpose, we introduce regular expression, a notation that can be
used to describe essentially all the tokens of programming language.
Secondly, having decided what the tokens are, we need some mechanism to recognize these
in the input stream. This is done by the token recognizers, which are designed using transition
diagrams and finite automata.
b) Position of Lexical Analyzer
The LA is the first phase of a compiler. It main task is to read the input character and produce
as output a sequence of tokens that the parser uses for syntax analysis.

Fig: Position of a Code Generator

Upon receiving a get next token command form the parser, the lexical analyzer reads the
input character until it can identify the next token. The LA return to the parser representation for the
token it has found. The representation will be an integer code, if the token is a simple construct such
as parenthesis, comma or colon.
LA may also perform certain secondary tasks as the user interface. One such task is striping
out from the source program the commands and white spaces in the form of blank, tab and new line
characters. Another is correlating error message from the compiler with the source program.
c) Why to separate Lexical analysis and parsing?
 Simplicity of design - for example, a parser that had to deal with comments and whitespace as
syntactic units would be considerably more complex than one that can assume comments and
whitespace have already been removed by the lexical analyzer.
 Improving compiler efficiency - specialized buffering techniques for reading input characters
can speed up the compiler significantly.
 Enhancing compiler portability - parts of the lexical analyzer may not be portable, but the
parser is always portable.
d) Lexical errors, are the errors thrown by your lexeme when unable to continue. Which means
that there's no way to recognise a lexeme as a valid token for you lexer. Syntax errors, on the
other side, will be thrown by your scanner when a given set of already recognised valid
tokens don't match any of the right sides of your grammar rules. simple panic-mode error
handling system requires that we return to a high-level parsing function when a parsing or
lexical error is detected.
Error-recovery actions are:
i. Delete one character from the remaining input.
ii. Insert a missing character in to the remaining input.
 iii. Replace a character by another character.
iv. Transpose two adjacent characters.
e) Token, Lexeme and Pattern
A token is a pair a token name and an optional token value
A pattern is a description of the form that the lexemes of a token may take (i.e. rule)
A lexeme is a sequence of characters in the source program that matches the pattern for a
token
Example:

14. Token Specification:

Computation:
Computation can be defined as finding solution to a problem from given inputs by means of
algorithm.
The theory of computation, a subfield of computer science and mathematics, deals with
finding solutions to problems from the given inputs.
Symbols:
A symbol is a single object and is an abstract entity that has no meaning by itself. It can be
character. Normally, characters from a typical keyboard are used as symbols.
Example: A, a, (alpha), (Lambda), etc..
Alphabets:
An alphabet is any finite, non-empty set of symbols/ characters. It is denoted byΣ. While
distinguishing two alphabets, the second one is usually denoted by Γ.
Example:
a. Σ= {0, 1} is the binary alphabet, consisting of the symbols 0 and 1.
b. Σ= {a, b, c} is an alphabet of three symbols.
c. Σ= {A, B,………, Z} is the uppercase English alphabet.

Strings:
A string is a finite sequence of symbols chosen from some alphabet. In other words, a string
is a finite sequence of symbols over an alphabet. It is usually denoted by W or S.
Example:
a. If Σ= {0, 1} then 01010, 1111, 11, 11, 10, 01… are some of the strings chosen
from this alphabet.
b. If Σ= {a, b} then ab, abab, aabb, are the words chosen from this alphabet.
Operations on Strings: Length, prefix, proper prefix, suffix, proper suffix, substring, proper
substring, concatenation.
Automaton:
An automaton (plural: automata) is a self-operating machine. The term "Automata" is derived
from the Greek word "αὐτόματα" which means "self-acting" or self-operational. It performs its
functions without direct human participation. It is self-operational.

Formal Languages
A formal language is an abstraction for general characteristics of programming languages that
can be defined as a string set, all of which are chosen from some particular alphabet . A formal
language is a set of finite length words drawn from some finite alphabet. The languages are denoted
by letter L, with or without a subscript.
Language notation:
a. L(M) is a language defined by a machine M, that accepts a certain set of strings.
b. L (G) is a language defined by grammar G that accepts a certain string set.
c. L(r) is a language defined by a regular expression ‘r’.
Examples:
a. Let ={Z} then the language of all possible strings is given by L1= {z, zz,
zzz, zzzz,…}. Here L1 does not contain null string.
b. Language containing the null string is { }
c. Null language: { } = .

Operations on languages:
There are totally 10 operations on languages. They are:
1. Union
2. Intersection
3. Complementation
4. Symmetric difference
5. Concatenation of language
6. Reversal of languages
7. Palindrome languages
8. Length sub-setting of a language
9. Kleene star/closure of languages
10. De Morgan’s Laws.

1. Union :
This is one of the simplest operation on two languages. As discussed earlier languages are set of
strings, and hence the union of two languages L1 and L2 is the set L1UL2. Mathematically, this is
represented as X ∈L1UL2, if and only if x∈L1 or x∈L2
Example
[Link] L1={0,01,011} and L2={∈,001}
then L1 U L2 = {∈,0,01,011}
b. Let L1={0,000,00000,…} and L2={∈,00,0000,…}
then L1 U L2 = {0}*
2. Intersection :
Suppose L1 and L2 are two languages over an alphabet .Then intersection of L1 and L2 is
denoted by L1 ∩L2, if and only if x ∈ L1 and x∈ L2.
Example
a. Let L1={∈} and L2=∅.Then L1∩L2=∅.
b. Let L be any language, then L∩ L’=∅.
3. Complementation :
It is an operation performed on a single language. Suppose L is a language over an alphabet∑,
then the compliment of L, denoted by L’, is the language consisiting of all those strings that are not
in L over the alphabet. Mathematically, this is expressed as x∈ L’ if and only if x ∈ ∑* - L
Example:
 a. If ∑={a,b} and L={a,b,aa} then the complement of L i.e., L’=∑*-L =
{∈,a,b,aa,bb,ab,ba,aaa,bbb,……}-{a,b,aa} = {∈, bb, ab, ba…}
b. Let L= {∈, 1, 11…} be a language over {0, 1}. Then, clearly L’ consists of all
strings, containing at least one 0.
4. Symmetric difference :
The operation, symmetric difference is no doubt an important but less
[Link],L1 and L2 are two languages defined over an alphabet ∑.Then the
symmetric difference of L1 and L2 is denoted by L1 L2,and is defined as L2 L2=(L1∪ 2 −
( 1 ∩ 2). Accordingly, elements of L1 L2 are contained either in L1 or L2 but not in both.
Example:
a. Let L be a language over an alphabet .Then clearly L ∅=L, L L=∅ , L ∑* = L’
and L L’=∑*
b. Let L1= {00, 0000,..} and L2= {11, 1111,..}.Then , L1 L2= {00, 11, 0000, 1111,…} = L1
U L2.
5. Concatenation of languages :
Concatenation of two languages L1 and L2 is the language L1∘L2, each element of which is a
string formed by gluing one string of L1 with another string of [Link], this is expressed
as: L1 ∘L2=L1L2= { ∘ y|x ∈L1 and y∈ L2}
Example:
a. Let L1={bc,bcc,cc} and L2={cc,ccc} then, L1∘L2= {bccc, bcccc, bcccccc, cccc, ccccc}
b. Let L1={zizz,…} and L2={0,1} then, L1∘L2={zzz,zzzzz,…}.
6. Reversal of languages :
The reversal of a language is an important operation that can be used in illustrating the working
procedure of various machines. This operation is similar to the reversal of a string operation.
Mathematically, this can be written as LR= {WR|W∈L}
Example:
a. If L={ab,bc,cd} then,
L = {ba, cb, dc}
R

b. If L={10,12,34} then,
L = {01, 21, 43}
R

7. Palindrome languages :
A language called Palindrome over ∑ = {a, b} is defined as:
Palindrome= {∈, all strings W, such that WR=W and W∈ ∑}.
Equivalently,
Palindrome={∈,a,b,aa,bb,aaa,bbb,aba,abba,aaaa,…}.
8. Length subsetting of a language :
Suppose L is a language over a fixed alphabet ∑ . Then for sake of convenience or compactness,
it may be required to specify the strings in L, of length less than or equal to a specific value or a fixed
size.
Example: Let L={1,11,111,1111,…} then L=4= {1111} and L<=4 = {1, 11, 111, 1111}.
9. Kleene star/Closure and Positive Closure of languages :
The Kleene star of language L is the language L*, consisting of all the strings produced by
concatenating any finite number of strings from L, together. In other words, kleene star denotes the
set of all words/strings of any length of any length from given language. Mathematically, this is
expressed as L*= {X|∈X1 X2… XR , with R≥0 and XR∈L}.
The Positive Closure of language L is the language L+. L+ = {X|∈X1 X2… XR , with R>0 and
XR∈L}.
Example:
a. If L={∈,z,zz,zzz,…} over ∑= {z} then L*= {∈, z, zz, zzz,…}, Where L*=L0 U L1 U L2
U…
b. ∅*={∈}.
c. If L= {z,zz,zzz,…} over ∑= {z} then L+ = {z, zz, zzz,…}, Where L+=L1 U L2 U…
10. De Morgan’s Laws :
It allows one to express the intersection of two languages over∑, in terms of the two operation
like, union and complementation. These are the fundamental laws in set theory.
Let L1, L2, L3 be any three languages, then
L1-(L2 U L3) = (L1-L3)
L1-(L2 ∩L3) = (L1-L2) U (L1-L3)
L1 ∩ L2 = (L1 C U L2 C) C.
Regular Expressions
Certain set of strings or languages can be represented in an algebraic fashion, and these
algebraic expressions of languages are called regular expression.
A regular expression is a string that describes the whole set of strings according to a certain
syntax rule. These expressions are used by text editors and utilities, to search bodies of text for
certain patterns.
A Regular Expression can be recursively defined as follows −
 ε is a Regular Expression indicates the language containing an empty string. (L (ε) = {ε})
 φ is a Regular Expression denoting an empty language. (L (φ) = { })
 x is a Regular Expression where L = {x}
 If X is a Regular Expression denoting the language L(X) and Y is a Regular Expression
denoting the language L(Y), then
 X + Y is a Regular Expression corresponding to the language L(X) ∪ L(Y) where
L(X+Y) = L(X) ∪ L(Y).
 X . Y is a Regular Expression corresponding to the language L(X) . L(Y) where
L(X.Y) = L(X) . L(Y)
 R* is a Regular Expression corresponding to the language L(R*)where L(R*) =
(L(R))*
 If we apply any of the rules several times from 1 to 5, they are Regular Expressions.
Some RE Examples
Regular
Regular Set
Expressions
(0 + 10*) L = { 0, 1, 10, 100, 1000, 10000, … }
(0*10*) L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L = {ε, 0, 1, 01}
Set of strings of a’s and b’s of any length including the null string. So L = { ε, a,
(a+b)*
b, aa , ab , bb , ba, aaa…….}
Set of strings of a’s and b’s ending with the string abb. So L = {abb, aabb, babb,
(a+b)*abb
aaabb, ababb, }
Set consisting of even number of 1’s including empty string, So L= {ε, 11, 1111,
(11)*
111111, }
String of a’s and b’s of even length can be obtained by concatenating any
(aa + ab + ba +
combination of the strings aa, ab, ba and bb including null, so L = {aa, ab, ba, bb,
bb)*
aaab, aaba, }
Any set that represents the value of the Regular Expression is called a Regular Set.
Properties of Regular Sets:
Property1. The union of two regular set is regular.
Proof − Let us take two regular expressions
RE1 = a(aa)* and RE2 = (aa)*
So, L1 = {a, aaa, aaaaa,. } (Strings of odd length excluding Null)
and L2 ={ ε, aa, aaaa, aaaaaa,. } (Strings of even length including Null)
 L1 ∪ L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,. }
(Strings of all possible lengths including Null)
RE (L1 ∪ L2) = a* (which is a regular expression itself)
Hence, proved.
Property2. The intersection of two regular set is regular.
Proof −
Let us take two regular expressions
RE1 = a(a*) and RE2 = (aa)*
So, L1 = { a,aa, aaa, aaaa, } (Strings of all possible lengths excluding Null)
L2 = { ε, aa, aaaa, aaaaaa,. } (Strings of even length including Null)
L1 ∩ L2 = { aa, aaaa, aaaaaa,. } (Strings of even length excluding Null)
RE (L1 ∩ L2) = aa(aa)* which is a regular expression itself.
Hence, proved.
Property3. The complement of a regular set is regular.
Proof −
Let us take a regular expression −
RE = (aa)*
So, L = {ε, aa, aaaa, aaaaaa, } (Strings of even length including Null)
Complement of L is all the strings that is not in L.
So, L’ = {a, aaa, aaaaa, } (Strings of odd length excluding Null)
RE (L’) = a(aa)* which is a regular expression itself.
Hence, proved.
Property4. The difference of two regular set is regular.
Proof −
Let us take two regular expressions −
RE1 = a (a*) and RE2 = (aa)*
So, L1 = {a, aa, aaa, aaaa, } (Strings of all possible lengths excluding Null)
L2 = { ε, aa, aaaa, aaaaaa,. } (Strings of even length including Null)
L1 – L2 = {a, aaa, aaaaa, aaaaaaa, }
(Strings of all odd lengths excluding Null)
RE (L1 – L2) = a (aa)* which is a regular expression.
Hence, proved.
Property5. The reversal of a regular set is regular.
Proof −
We have to prove LR is also regular if L is a regular set.
Let, L = {01, 10, 11, 10}
RE (L) = 01 + 10 + 11 + 10
LR = {10, 01, 11, 01}
RE (LR) = 01 + 10 + 11 + 10 which is regular
Hence, proved.
Property6. The closure of a regular set is regular.
Proof −
If L = {a, aaa, aaaaa, } (Strings of odd length excluding Null)
i.e., RE (L) = a (aa)*
L* = {a, aa, aaa, aaaa , aaaaa,… } (Strings of all lengths excluding Null)
RE (L*) = a (a)*
Hence, proved. (also seen the Positive Closure)
Property7. The concatenation of two regular sets is regular.
Proof −
Let RE1 = (0+1)*0 and RE2 = 01(0+1)*
Here, L1 = {0, 00, 10, 000, 010, } (Set of strings ending in 0)
and L2 = {01, 010,011,. } (Set of strings beginning with 01)
Then, L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,. }
Set of strings containing 001 as a substring which can be represented by an RE − (0 +
1)*001(0 + 1)*
Hence, proved.
Identities Related to Regular Expressions:
Given R, P, L, Q as regular expressions, the following identities hold −
 φ* = ε
 ε* = ε
 RR* = R*R
 R*R* = R*
 (R*)* = R*
 RR* = R*R
 (PQ)*P =P(QP)*
 (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*
 R + φ = φ + R = R (The identity for union)
 R ε = ε R = R (The identity for concatenation)
 φ L = L φ = φ (The annihilator for concatenation)
 R + R = R (Idempotent law)
 L (M + N) = LM + LN (Left distributive law)
 (M + N) L = ML + NL (Right distributive law)
 ε + RR* = ε + R*R = R*
Regular Definition:
For notational convenience, we may wish to give names to regular expressions and to define
regular expressions using these names as if they were symbols. Identifiers are the set or string of
letters and digits beginning with a letter. The following regular definition provides a precise
specification for this class of string.
• Example:
letter_ -> A | B | … | Z | a | b | … | z |
digit -> 0 | 1 | … | 9
id -> letter_ (letter_ | digit)*

15. Token Recognition

Transition Diagrams:
Transition Diagram has a collection of nodes or circles, called states. Each state represents a
condition that could occur during the process of scanning the input looking for a
lexeme that matches one of several patterns. Edges are directed from one state of the transition
diagram to another. each edge is labeled by a symbol or set of symbols.
If we are in one state s, and the next input symbol is a, we look for an edge out of state s
labeled by a. if we find such an edge ,we advance the forward pointer and enter the state of the
transition diagram to which that edge leads.
Some important conventions about transition diagrams are
1. Certain states are said to be accepting or final .These states indicates that a lexeme has been found,
although the actual lexeme may not consist of all positions b/w the lexeme Begin
and forward pointers we always indicate an accepting state by a double circle.
2. In addition, if it is necessary to return the forward pointer one position, then we shall additionally
place a * near that accepting state.
3. One state is designed the state, or initial state., it is indicated by an edge labeled “start” entering
from nowhere. the transition diagram always begins in the state before any input symbols have been
used.
Example: Transition diagram for Relation Operators

Transition diagram for numbers

Transition diagram for Identifiers

16. Bootstrapping
 Bootstrapping is widely used in the compilation development.
 Bootstrapping is used to produce a self-hosting compiler. Self-hosting compiler is a type of
compiler that can compile its own source code.
 Bootstrap compiler is used to compile the compiler and then you can use this compiled
compiler to compile everything else as well as future versions of itself.
A compiler can be characterized by three languages:
 1. Source Language
2. Target Language
3. Implementation Language
The T- diagram shows a compiler SC IT for Source S, Target T, implemented in I.

Follow some steps to produce a new language L for machine A:

1. Create a compiler SC AA for subset, S of the desired language, L using language "A" and that
compiler runs on machine A.

2. Create a compiler LC A for language L written in a subset of L.

S

3. Compile LC SA using the compiler SC AAto obtain LC [Link] A

isA a compiler for language L, which runs
on machine A and produces code for machine A.

The process described by the T-diagrams is called bootstrapping.

17. Cross Compiler

A cross compiler is a compiler capable of creating executable code for a platform other than the
one on which the compiler is running. For example, a cross compiler executes on machine X and
produces machine code for machine Y.

Where is the cross compiler used?

 In bootstrapping, a cross-compiler is used for transitioning to a new platform. When
developing software for a new platform, a cross-compiler is used to compile necessary
tools such as the operating system and a native compiler.
 For microcontrollers, we use cross compiler because it doesn’t support an operating
system.
 It is useful for embedded computers which are with limited computing resources.
 To compile for a platform where it is not practical to do the compiling, a cross-compiler
is used.
 When direct compilation on the target platform is not infeasible, so we can use the cross
compiler.
  It helps to keep the target environment separate from the built environment.

T-Diagram for Cross-compiler

A compiler is characterized by three languages:
1. The source language that is compiled.
2. The target language T is generated.
3. The implementation language that is used for writing the compiler.
How does cross-compilation work?
A cross compiler is a compiler capable of creating executable code for a platform other than the
one on which the compiler is running. In paravirtualization, one computer runs multiple operating
systems and a cross compiler could generate an executable for each of them from one main source.

Working of Cross-Compiler
How compiler is different from a cross-compiler?
The native compiler is a compiler that generates code for the same platform on which it runs and
on the other hand, a Cross compiler is a compiler that generates executable code for a platform
other than one on which the compiler is running. Check out this article for more
information Difference between Native compilers and Cross compilers.

18. LEX tool:

Lex is a program designed to generate scanners, also known as tokenizers, which recognize lexical
patterns in text. Lex is an acronym that stands for "lexical analyzer generator." It is intended
primarily for Unix-based systems.
Lex is a tool in lexical analysis phase to recognize tokens using regular expression. Lex tool itself is
a lex compiler.
Use of Lex

lex.l is an a input file written in a language which describes the generation of lexical analyzer. The
lex compiler transforms lex.l to a C program known as [Link].c.
[Link].c is compiled by the C compiler to a file called [Link].
The output of C compiler is the working lexical analyzer which takes stream of input characters and
produces a stream of tokens.
yylval is a global variable which is shared by lexical analyzer and parser to return the name and an
attribute value of token.
The attribute value can be numeric code, pointer to symbol table or nothing.
Another tool for lexical analyzer generation is Flex.
Structure of Lex Programs
Lex program will be in following form
declarations
%%
translation rules
%%
auxiliary functions
Declarations This section includes declaration of variables, constants and regular definitions.
Translation rules It contains regular expressions and code segments.
Form: Pattern {Action}
Pattern is a regular expression or regular definition.
Action refers to segments of code.
Auxiliary functions This section holds additional functions which are used in actions. These
functions are compiled separately and loaded with lexical analyzer.
Lexical analyzer produced by lex starts its process by reading one character at a time until a valid
match for a pattern is found. Once a match is found, the associated action takes place to produce
token. The token is then given to parser for further processing.
Sample Lex Program:
delim [\t]
ws {delim}+
letter [A-Za-z]
digit [0-9]
id {letter}({letter}|{digit})*
num {digit}+(\.{digit}+)?(E[+-]?{digit}+)?
%%
ws {printf("no action");}
if|else|then {printf("%s is a keyword",yytext);} // TYPE 32 KEYWORDS
{id} {printf("%s is a identifier",yytext);}
{num} {printf(" it is a number");}
"<" {printf("it is a relational operator less than");}
"<=" {printf("it is a relational operator less than or equal");}
">" {printf("it is a relational operator greater than");}
">=" {printf("it is a relational operator greater than");}
"==" {printf("it is a relational operator equal");}
"<>" {printf("it is a relational operator not equal");}
%%
main()
{
yylex();
}

OUTPUT

lex lexicalfile.l
cc [Link].c -ll
if
if is a keyword
number
number is a identifier
254
It is a number
<>
it is a relational operator not equal
^Z