WRITE RES FOR THE FOLLOWING LANGUAGES:

• Accepting all combinations of a’s over the set ={a}

Ans: a*
• Accepting all combinations of a’s over the set ={a} except null string
Ans: a+
• Accepting any no of a’s and b’s
Ans: (a+b)* or (a/b)*
• Strings ending with 00 over the set {0,1}
Ans: (0+1)*00
• Strings starts with 1 and ends with 0 over the set {0,1}
Ans: 1(0/1)*1
• Any no of a’s followed by any no of b’s then followed by any no of c’s
Ans: a*b*c*
• starting and ending with a and having any combination of b's in between.
Ans: a b* b
• Starting with a but not having consecutive b's.
Ans: L = {a, aba, aab, aba, aaa, abab, .....}
R = {a + ab}*
• The language accepting all the string in which any number of a's is followed by any
number of b's is followed by any number of c's.
Ans: R = a* b* c*
• The language over ∑ = {0} having even length of the string.
Ans: R = (00)*
• For the language L over ∑ = {0, 1} such that all the string do not contain the substring
01.
Ans: The Language is as follows: L = {ε, 0, 1, 00, 11, 10, 100, .....}
R = (1* 0*)
• For the language containing the string over {0, 1} in which there are at least two
occurrences of 1's between any two occurrences of 1's between any two occurrences of 0’s.
Ans: (0111*0)*.
Similarly, if there is no occurrence of 0's, then any number of 1's are also allowed. Hence
the r.e. for required language is:
R = (1 + (0111*0))*
• The regular expression for the language containing the string in which every 0 is
immediately followed by 11.
Ans:R = (011 + 1)*
• String which should have at least one 0 and at least one 1
Ans: R = [(0 + 1)* 0 (0 + 1)* 1 (0 + 1)*] + [(0 + 1)* 1 (0 + 1)* 0 (0 + 1)*]
• Describe the language denoted by following regular expression (b* (aaa)* b*)*
Ans: The language consists of the string in which a's appear triples, there is no restriction
on the number of b’s.
ARDEN'S THEOREM
Statement: Let B and C are two regular expressions. If C does not contain null string,
then A=B+AC has a unique solution A= BC*
Proof: Given that B and C are two regular expressions and C does not contain null string
Case(i): Let us verify whether A=BC* is a solution of A=B+AC
Substitute A =BC* in the above equation
A=B+AC
A=B+BC*C=B(ε +C*C)=BC* since ε+RR*=R*
BC*=BC*
LHS=RHS==>
Therefore A=BC* is a solution of A=B+AC
Case (ii): Let us Prove That A=BC* is a unique solution of A=B+AC
A=B+AC
=B+(B+AC)C=B+BC+AC2
=B+BC+(B+AC)C= B+BC+BC2 +AC3
= B+BC+BC2 +BC3 +AC4
=B(ε+C+C2 +C3 +……)
= BC*
Therefore A=BC* is a unique solution
Note: Assumptions for Applying Arden’s Theorem
• The transition diagram must not have NULL transitions
• It must have only one initial state
2.5 Construct RE from FA Using Arden‘s theorem
• If there are n number of states in the FA then we will get n number of equations.
• The equations are constructed in the following way:
• State name= state name from which inputs are coming. Input symbol .i.e.,
αji represents the transition from qj to qi then qi = αji . qj
• If qj is a start state then we have:
• qi = αji * qj + ε
• Solve the above equations to obtain final state which contains input symbols only.
Ex: Construct the regular expression for the given DFA
Solution:
Let us write down the equations q1 = q1 0 + ε
Since q1 is the start state, so ε will be added, and the input 0 is coming to q1 from q1
hence we write State = source state of input × input coming to it
Similarly, q2 = q1 1 + q2 1 q3 = q2 0 + q3 (0+1)
Since the final states are q1 and q2, we are interested in solving q1 and q2 only. Let us
see q1 first q1 = q1 0 + ε
We can re-write it as q1 = ε + q1 0
Which is similar to R = Q + RP, and gets reduced to R = OP*.

Assuming R = q1, Q = ε, P = 0 We get q1 = ε.(0)* q1 = 0* (ε.R*= R*)

Substituting the value into q2, we will get
q2 = 0* 1 + q2 1 q2 = 0* 1 (1)* (R = Q + RP → Q P*)
The regular expression is given by
r = q1 + q2 = 0* + 0* 1.1* r = 0* + 0* 1+ (since 1.1* = 1+)
Construction of FA from RE: There are two methods to construct FA from RE. They are
i) Top down approach and
ii) Bottom up approach.

Construction of FA from RE -Top down Approach:

This is divided into several steps as given in the following.
Step-1: Take two states, one is the beginning state and another is the final state. Make a
transition from the beginning state to the final state and place the RE in between the
beginning and final states

Step-2:If in the RE there is a + (union) sign, then there are parallel paths between the two
states

Step-3: If in the RE there is a .(dot) sign, then one extra state is added between the two
states.
Step-4: If in the RE there is a ‘*’ (closure) sign, then a new state is added in between. A
loop is added on the new state and the label Λ is put between the first to new and
new to last.

Ex: Construct Finite Automata equivalent to the Regular Expression

L = ab(aa + bb)(a + b)* b.

Step I: Take a beginning state q0 and a final state qf. Between the beginning and final
state place the regular expression.

Step II: There are three dots (.) between ab, (aa + bb), (a + b)*, and b. Three extra states
are added between q0 and qf.

Step III: Between ‘a’ and ‘b’ there is a dot (.), so extra state is added

Step IV: In aa + bb there is a +, therefore there is parallel edges between q1 and q2.
Between q2 and q3 there is (a + b)*. So, extra state q5 is added between q2 and q3.
Loop with label a, b is placed on q5 and Λ transition is made between q2, q5 and
q5, q3.

Step V: In aa and bb there are dots (.). Thus two extra states are added between q1 and
q2 (one for aa and another bb). The final finite automata for the given regular expression is
given below.
Ex: Construct an FA equivalent to the RE: L = (a + b)*(aa + bb)(a + b)*.
Construction of FA from RE –Bottom-Up Approach (Thomson Construction):
Step-1: For input a ∈ ∑, the transition diagram is

Step-2: If r1 and r2 are two RES then the transition diagram for the RE r1 + r 2 is

Step-3: If r1 and r2 are two RES then the transition diagram for the RE r1 . r 2 is

Step-4: If r is a RE then the transition diagram for r* is

Ex: Construct Finite Automata equivalent to the Regular Expression
L = ab(aa + bb)(a + b)*a.
Solution:
Step I: The terminal symbols in L are ‘a’ and ‘b’. The transition diagrams for ‘a’ and ‘b’
are given below:

Step II: The transition diagrams for ‘aa’, ‘ab’, ‘bb’ are given below

Step III: The transition diagram for (a+b) is given below

Step IV: The transition diagram for (a+b)* is given below

EQUIVALENCE OF TWO RES:
For every RE there is a finite automata. If the FA constructed both of the REs are same
then we can say that two REs are equivalent
Ex: Prove that the following REs are equivalent. L1 = (a + b)* L2 = a*(b*a)*
Solution:
Construct FA for L1:
Construct FA for L2:
RE TO RG CONVERSION
• Construct an equivalent FA for the given RE
The no of non-Terminals of the grammar will be equal to the no of states of FA
• For all transition functions (a) if δ(qi,a)=qj is not in F then the production is of the
form A→aB (b) if δ(qi,a)=qj is in F then the productions are of the form A→aB and
A→a, where A &B are corresponding to states qi and qj respectively.
• The start symbol of the grammar corresponding to initial state of finite automata
Ex: Construct Regular grammar for the RE a*(a+b)b*
RG for the above RE is
A→aA/aB/bB/a/b
B→bB/b
Ex: Construct RG for the RE ab(a+b)*
RG is
A→aB
B→bC/b
C→aC/bC/a/b
Constructing FA from Regular Grammar:
FA can directly be constructed from regular grammar. This can be considered as a
reverse process of constructing the FA from an RE.
Step I:
i) If the grammar does not produce any null string, then the number of states of the FA
is equal to the number of non-terminals of the regular grammar +1. Each state of the
FA represents each non-terminal and the extra state is the final state of the FA. If it
produces a null string, then the number of states is the same as the number of
nonterminals.
ii) The initial state of the FA is the start symbol of the regular grammar.
iii) If the language generated by the regular grammar contains a null string, then the
initial state is also the final state of the constructing FA.
Step II:
For a production in the form A → aB, make a δ function δ(A, a) → B. There is an arc
from state A to state B with label a.
ii) For a production in the form A → a, make a δ function δ(A, a) → final state.
iii) For a production A → ∈, make a δ function δ(A, ∈) → A, and A is the final state.
Ex: Convert the following regular grammar into FA:
S→ aA/bS A → bB/a B → aS/b.
Solution: In the grammar, there are three non-terminals, namely S, A, and B. So, the
number of states of the FA will be four(3+1). Let us name the final state as C.
For the production S → aA/bS, the transitional diagram becomes

The resulting two FAs are same. Hence the RE’s are also same.
Ex: Prove that the following REs are equivalent. L1 = 1*(011)*(1*(011)*)*
L2 = (1 + 011)*
For the production A → bB/a, the transitional diagram including the previous one is

For the production B → aS/b, the transitional diagram including the previous one
looks like
Converting Finite Automaton to Regular Grammar:
Let L be the language for some DFA M = (Q, S, δ, q0, F). Let us assume that q0 is not
the final state. For this we have to find grammar G such that L(G) = L(M).
Let G = (Q, S, P, q0) where
i) Q is the set of states, which are considered as Non-Terminals in the grammar.
ii) The input symbols are considered as the terminal symbols.
iii) The start state of NFA is considered as the starting symbol in the grammar.
iv) The productions are defined from transitions δ: as
• If there is a transition of the form δ (q, a) = p, then add a production q→ap if p is
some non-final state.
• If there is a transition of the form δ (q, a) = p, then add a production q→ap/a if p is
some final state
Linear Grammar:
A grammar is called linear grammar if it is context free, and the RHS of all
productions
have at most one non-terminal.
Ex: S → abSc/∈
There are two types of linear grammar:
1. Left linear grammar: A linear grammar is called left linear if the RHS non-terminal
in each productions are at the left end. In a linear grammar if all productions are in the
form A → Bα or A → α, then that grammar is called left linear grammar. Here, A and
B are non-terminals and α is a string of terminals.
2. Right linear grammar: A linear grammar is called right linear if the RHS non-
terminal in each productions are at the right end. In a grammar if all productions are
in the form A → αB or A → α, then that grammar is called right linear grammar. Here
A and B are non-terminals and α is a string of terminals.
Construction of Left Linear Grammar: To construct a left linear grammar, first we
reverse the given DFA. Then we construct right linear grammar for the reversed DFA
and then reverse the productions to get left linear grammar.
Ex: Find right linear grammar for the following DFA
For the given DFA, the equivalent right linear grammar is
V = {q0, q1, q2, q3} T = {0, 1} S = q0
P = {q0→1q0 | 0q1, q1→0q2 | 1q0, q2→0q3 | 1q0 | 0 , q3→1q3 | 0q3, | 1 | 0}
Ex: Find left linear grammar for the following DFA

To find the left linear grammar, first we reverse the DFA by reversing all the edges;
and
making the initial state as final, and the final state as initial.

For reversed DFA, the equivalent right linear grammar is

V = {q0, q1, q2, q3}, T = {0, 1}, S = q3
P = {q3→1q2 | 0q1, q1→0q3 | 1q0 | 1 , q2→0q0 | 1q3 | 0, q0→1q1 | 0q2}
To get the left linear grammar reverse all the productions of the above grammar.
P = {q3→ q2 1| q10, q1→ q30 | q01 | 1, q2→ q00 | q31 | 0, q0→ q11 | q20}
PUMPING LEMMA FOR RLS
• The pumping lemma is generally used to prove certain languages are not regular
• Language is said to be regular: If a DFA,NFA or epsilon NFA can be constructed to
exactly accept a language
• If a RE can be constructed to exactly generate the strings in a language.
Formal Definition of Pumping Lemma:
• if L is a regular language represented with automaton with maximum of n states ,
then there is a word in L such that the length |Z|>=n, we may write Z=UVW in such a
way that |UV|<+n, |V|>=1, and for all i>=0, UVi W is in L.
• Ex: Prove that L = {aibi | i ≥ 0} is not regular.
At first, we assume that L is regular and n is the number of states.
Let z= aabb=uvw
Where u=a, v= ab, w=b
Whein i=0, uviw=uw=ab is in L
When i=1, uviw=uvw=aabb is in l
When i=2, uviw=uv2w=aababbis not in L
Hence L is not Regular
CLOSURE PROPERTIES OF RLS
1) Context-free languages are closed under
Union: Let L1 and L2 be two context free languages. Then L1 ∪ L2 is also context
free.
Example
• Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab
• Let L2 = { cmdm , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε
• Union of L1 and L2, L = L1 ∪ L2 = { anbn } ∪ { cmdm }
• The corresponding grammar G will have the additional production S → S1 | S2
Concatenation: If L1 and L2 are context free languages, then L1L2 is also context
free.
Example: Union of the languages L1 and L2, L = L1L2 = { anbncmdm }
The corresponding grammar G will have the additional production S → S1 S2
Kleene Star: If L is a context free language, then L* is also context free.
Example
• Let L = { anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε
• Kleene Star L1 = { anbn }*
• The corresponding grammar G1 will have additional productions S1 → SS1 | ε
Context-free languages are not closed under Intersection: If L1 and L2 are context
free languages, then L1 ∩ L2 is not necessarily context free.
Intersection with Regular Language − If L1 is a regular language and L2 is a context
free language, then L1 ∩ L2 is a context free language.
Complement − If L1 is a context free language, then L1’ may not be context free
Decision Problems of Regular Expression: Decision problems are the problems which
can be answered in ‘yes’ or ‘no’. FA are one type of finite state machines which
contain a finite number of memory elements.
Thus, it can memorize only finite amount of information. FA can answer to those
decision problems which require only a finite amount of memory.
The decision problems related to RE are
1. Whether a string x belongs to a regular expression R? (x ∈ R?)
2. Whether the language set of an FA M is empty? [L(M) = ∅ ?]
3. Whether the language set of an FA is finite? [L(M) is finite?]
4. Whether there exists any string accepted by two FA, M1 and M2?
5. Whether the language set of an FA M1 is a subset of the language set of another FA
M2? [L(M1) ⊆ L(M2)?]
6. Whether two FA M1 and M2 accept the same language? [L(M1) = L(M2)]
7. Whether two REs R1 and R2 are from the same language set?
8. Whether an FA is the minimum state FA for a language L?
Applications of Regular Expression:
RE is mainly used in lexical analysis of compiler design. In the programming
language, we need to declare a variable or identifier. That identifier must start with a
letter followed by any number of letters or digits. SVCE TIRUPATI

Ex1:The structure of the identifier is represented by RE. The definition of an identifier

in a programming language is
letter → A | B | ... | Z | a | b | ... | z
digit → 0 | 1 | ... | 9
id → letter (letter | digit) *
Ex2: The definition of an unsigned number in a programming language is
digit → 0 | 1 | ... | 9
digits → digit +
 opt-fraction → (. digits) *
opt-exponent → (E (+ | -) * digits) *
unsigned-num → digits opt-fraction opt-exponent
Ex3: pattern searching from a given text.