Module 3
1. Define Regular Expression with an example.
A Regular Expression (RE) is a formal notation used to define regular languages. It consists of symbols and operators that
specify a pattern in strings. Regular Expressions s are used in pattern matching and can be recognized by finite automata.
Example:
Consider the regular expression *(ab)c:
(a + b)* allows repetition of a or b any number of times, including zero.
The final c is mandatory at the end.
Accepted Strings:
c, ac, bc, abc, aabbc, ababac
This RE defines all strings that consist of any sequence of a and b , followed by a mandatory c . It represents a regular
language that can be recognized by a Deterministic Finite Automaton (DFA).
2. Define a regular expression representing strings of a's and b's having odd length.
(a + b)((a + b)(a + b))
∗
3. Sketch a Finite Automata from given regular expression 10 + (0 + 11)0* 1.
4 Explain the regular expression for the language L over ∑ = {0, 1} such that all the string do not
contain the substring 01.
∗
1 0
∗
5 Develop a DFA from the following regular expression a + bb + bab*a
6. Describe closure properties of regular sets.
A regular set is a set of strings recognized by a finite automaton or described by a regular expression. Regular languages
follow closure properties, meaning they remain regular under certain operations.
Module 3 1
Regular languages are closed under following operation
Kleene Closure
Positive Closure
Complement
Reverse Operator
Prefix Operator
Suffix Operator
Concatenation
Union
Intersection
Set Difference Operator
Symmetric Difference
7. Solve that (0*1*)* = (0+1)*
LHS, (0∗ 1∗ )∗
we know, (P+Q)* = (P* + Q*)* = (P+Q)*
so therefore, (0∗ 1∗ )∗ = (0 + 1)
∗
8. Construct an equivalent FA for the given regular expression
(0+1)*(00+11)(0+1)*
9. Construct the regular expressions represent the following:
a) The set of all strings over {0,1} beginning with 00.
b) The set of all strings over {0,1} ending with 00 and beginning with 1.
a) The set of all strings over {0,1} beginning with 00.
00(0 + 1)
∗
b) The set of all strings over {0,1} ending with 00 and beginning with 1.
∗
1(0 + 1) 00
10. Construct NFA with epsilon moves for the regular expression :
ab* (a+b)* + ba*
Module 3 2
11. Discover the regular expression from the finite Automata.
A = ε + B .b + C .a —————-(1)
B = A.a ————————————(2)
C = A.b —————————————(3)
D = B .a + C .b + D.(a + b) ———-(4)
A = ε + A.a.b + A.b.a —————- (applying equation 2 and 3)
A = ε + A(ab + ba)
A = ε.(ab + ba)
∗
A = (ab + ba)
∗
B = (ab + ba) a
∗
C = (ab + ba) b
∗
D = B .a + C .b + D(a + b)
∗
D = (ab + ba) aa + (ab + ba) bb + D(a + b)
∗
∗
D = (ab + ba) (aa + bb) + D(a + b)
∗
D = (ab + ba) (aa + bb)(a + b)
∗
as D is the final state in the DFA, therefore the Regular expression = (ab + ba)∗ (aa + bb)(a + b)∗
12. Explain the complement of a regular language is also regular.
The complement of a regular language L, denoted as L' , consists of all strings not belonging to L . If L is regular, then L'
is also regular.
Proof Using DFA:
Module 3 3
1. A regular language is recognized by a Deterministic Finite Automaton (DFA).
2. In a DFA, the set of final states represents the accepted language L .
3. To construct the complement language L', we swap the final and non-final states in the DFA.
4. Since DFA-based recognition remains valid under this transformation, L' is also regular.
Example:
If L represents {0, 1} strings ending in '0', then L' represents {0, 1} strings not ending in '0'.
Both languages can be recognized by a DFA, proving closure under complementation.
Since regular languages are recognized by finite automata, they remain regular under complement operation.
13. Evaluate the conversion of the following expression to NFA with € transitions. 0*+1101
14. Explain Difference between Grammar and Regular expression.
Grammar:
A grammar is a formal set of rules that define the structure of a language. It consists of variables, terminals, production
rules, and a start symbol. Grammars can generate languages beyond regular languages, including context-free and
context-sensitive languages.
Regular Expression:
A regular expression (RE) is a symbolic notation used to describe regular languages. It consists of concatenation, union,
and Kleene star operations and can be recognized by finite automata.
Key Differences:
Feature Grammar Regular Expression
Definition Defines language using rules Defines patterns in strings
Power Can represent non-regular languages Only describes regular languages
Representation Uses production rules (like S → aSb | ε ) Uses operators ( a* , a|b , ab )
Recognized By Pushdown Automata (for CFGs) Finite Automata
Thus, grammars are more expressive than regular expressions, as regular expressions only define regular languages,
whereas grammars can define context-free and more complex languages.
15. Explain a regular expression that represent the language
L = {a
m n
b ∣m >= 1, n >= 1, nm >= 3} .
For this question, we see n>=1 m>=1 which is cool, but twist comes with this condition nm>=3
So we have to complete for when n=1 and m=1, the minimum condition with the third condition
let’s see the possibilities
Case 1: n=1, m=1, Not possible simply cause nm<=3(nm=1)
Module 3 4
Case 2: n=1, m=2, Not possible simply cause nm<=3(nm=2)
Case 3: n=1, m=3, Very much possible simply cause nm>=3(nm=3)
So, min condition for n=1 is satisfied,
Let’s take for m=1
Case 1: n=1,m=1, Not possible simply cause nm<=3(nm=1)
Case 2: n=2,m=1, Not possible simply cause nm<=3(nm=2)
Case 3: n=3,m=1, Very much possible simply cause nm>=3(nm=3)
So, min condition for m=1 is satisfied,
The Answer will be aa∗ b3 b ∗ +a3 a ∗ bb∗
16. Explain a regular expression that represent the language
L = {a
2m 2n
b ∣m >= 0, n >= 0} .
(aa)* (bb)* + (bb)* (aa)*
17. Explain a NFA for the regular expression (a + b)aa(a + b)∗ and draw the same using
Thomson's construction method.
18. Explain a NFA for the regular expression (a+b)* using Thomson’s construction and then
convert that NFA to DFA.
Module 3 5
19. Show a NFA using Thompson's construction of the following RE. (a+b)*a(a+b)
20. Show that (1 + 00∗ 1) + (1 + 00∗ 1)(0 + 10∗ 1)(0 + 10∗ 1) ∗ ∗
= 0 1(0 + 10 1)
∗
LHS = (1 + 00∗ 1) + (1 + 00∗ 1)(0 + 10∗ 1)∗ (0 + 10∗ 1)
∗ ∗
(1 + 00 1)[ε + (0 + 10 1) (0 + 10 1)]
∗ ∗
∗ ∗
(1 + 00 1)(0 + 10 1)
∗
∗
(ε1 + 00 1)(0 + 10 1)
∗ ∗
Module 3 6
∗
(ε + 00 )1(0 + 10 1)
∗ ∗
∗
0 1(0 + 10 1)
∗ ∗
⇒ RHS
Hence Proved
21. Prove that CFLs are not closed under intersection and complement operation.
Proof: Context-Free Languages (CFLs) Are Not Closed Under Intersection and Complement
1. CFLs Are Not Closed Under Intersection
Counterexample:
Consider the two context-free languages over {a, b} :
L₁ = { aⁿbⁿcᵐ | n, m ≥ 0 } → Strings with equal a s and b s, followed by any number of c s.
L₂ = { aⁿbᵐcᵐ | n, m ≥ 0 } → Strings with equal b s and c s, preceded by any number of a s.
Both L₁ and L₂ are context-free. Their intersection is:
L₁ ∩ L₂ = { aⁿbⁿcⁿ | n ≥ 0 } , which requires equal numbers of a , b , and c .
However, { aⁿbⁿcⁿ | n ≥ 0 } is not a CFL (it requires a non-context-free comparison of three symbols).
Thus, CFLs are not closed under intersection.
2. CFLs Are Not Closed Under Complement
Since CFLs are closed under union, if they were closed under complement, they would also be closed under intersection
(by De Morgan's Law):
L₁ ∩ L₂ = ~(~L₁ ∪ ~L₂) .
But we have already shown that CFLs are not closed under intersection.
Therefore, they cannot be closed under complement.
Conclusion:
Intersection of CFLs may not be a CFL, proving non-closure.
Complement would imply intersection closure, which is false.
Thus,
CFLs are not closed under intersection and complement operations.
22. State and prove Arden’s theorem.
Statement
Let P and Q be regular expressions over an alphabet Σ. If P does not contain ε (the empty string), then the equation:
R = Q + RP
has a unique solution given by:
R = QP
∗
where P ∗represents the Kleene star operation.
Proof of Arden's Theorem
Starting with the equation:
R = Q + RP
We substitute R recursively:
R = Q + (Q + RP )P
R = Q + QP + RPP
Continuing this process:
R = Q + +QP
2
+ QP
3
+ …
Since P* represents (ε + P + P² + P³ + ...), we can factor:
R = Q(ε + P + P
2
+ P
3
+ ...)
Module 3 7
which simplifies to:
R = QP
∗
Thus, R = QP
∗
is the unique solution to the equation R = Q + RP .
23. Consider the following transition diagram of a FA. Prove that the strings recognized are ( a +
a(b +aa )* b)* a (b +aa)*a.
1. Q 1 = ε + Q 1 .a + Q 2 .b
2. Q 2 = Q 1 .a + Q 2 .b + Q 3 .a
3. Q 3 = Q 1 .a
Step 1: Express Q3 in Terms of Q1
From equation (3):
Q 3 = Q 1 .a
Substituting this into equation (2):
Q2 = Q1 .a + Q2 .b + (Q1 .a).a
Q2 = Q1 .a + Q2 .b + Q1 .aa
Q2 = Q1 (a + aa) + Q2 .b
Using Arden’s Theorem:
Q2 = Q1 (a + aa)b
∗
Step 2: Substitute Q2 into Equation (1)
Q1 = ε + Q1 .a + (Q1 (a + aa)b )b
∗
Q1 = ε + Q1 .a + Q1 (a + aa)b ∗
2
Factor A:
Q1 = ε + Q1 (a + (a + aa)b )
∗
Using Arden's Theorem:
Q1 = (a + (a + aa)b )
∗ ∗
Step 3: Match with the Given Expression
Our target expression is:
( a + a(b + aa )* b)* a (b + aa)*a
Let's verify the structure:
Our Q1
= (a + (a + aa)b )
∗ ∗
matches the (a + a(b + aa)b)∗ part.
The extra a(b + aa)a∗ follows naturally from how the transitions propagate.
Thus, our derived regular expression is equivalent to the given one after transformation. ✅
24. Simplify the following FA to equivalent Regular Expression
Module 3 8
Q1 = ε + Q2 .b + Q3 .a
—————-(1)
Q 2 = Q 1 .a
————————————(2)
Q 3 = Q 1 .b
—————————————(3)
Q4 = Q2 .a + Q3 .b + Q4 .(a + b)
———-(4)
Q1 = ε + Q1 .a.b + Q1 .b.a
—————- (applying equation 2 and 3)
Q1 = ε + Q1 (ab + ba)
Q1 = ε.(ab + ba)
∗
Q1 = (ab + ba)∗
as Q1 is the final state, therefore, the Regular Expression is Q1
= (ab + ba)∗
25. Simplify the following FA to equivalent Regular Expression
Q1 = ε + Q1 .0
————————- (i)
Q2 = Q1 .1 + Q2 .1
——————- (ii)
Q3 = Q2 .0 + Q3 (0 + 1)
———- (iii)
Q1 = ε + Q1 .0
Q1 = ε.0
∗
⇒ 0∗
Q2 = Q1 .1 + Q2 .0
∗
Q2 = 0 1 + Q2 .0
Q2 = (0 1)(1)
∗ ∗
⇒ 0∗ 11∗
As Q2 is the Final State, The regular expression is: 0∗ 11∗
26. Explain Closure and Associative property.
Closure Property:
Module 3 9
Regular expressions are closed under various operations, meaning that applying these operations to regular expressions
results in another regular expression. Regular expressions are closed under:
Union ( R₁ + R₂ ) → Combining two regular expressions produces another regular expression.
Concatenation ( R₁R₂ ) → Joining two regular expressions still forms a regular language.
Kleene Star ( R* ) → Repeating a regular expression an arbitrary number of times remains regular.
Associative Property:
Regular expressions follow associativity for union and concatenation:
Union: (R₁ + R₂) + R₃ = R₁ + (R₂ + R₃)
Concatenation: (R₁R₂)R₃ = R₁(R₂R₃) , meaning order of grouping does not change the resulting language.
For example, with R₁ = "a" , R₂ = "b" , and R₃ = "c" ,
(R₁R₂)R₃ = "abc"
R₁(R₂R₃) = "abc"
showing concatenation is
associative.
27. Evaluate an NFA which accepts strings of a's and b's starting with ab and draw the same using
Thomson's construction method.
28. Develop a NFA for the regular expression a* + b* + c* and draw the same using Thomson's
construction method.
Module 3 10
Module 3 11
