Regular language and Regular expression

A Tutorial
By
Animesh Chaturvedi

1. Automata Theory and Logic
Regular Language & Regular Expression
A TUTORIAL
BY
ANIMESH CHATURVEDI
AT
INDIAN INSTITUTE OF TECHNOLOGY INDORE (IIT -I)

2. DFA, NFA, Regular Expression (RegEx)
and Regular Language (RegLang)
A DFA represent a Regular Expression language

3. RegularExpressionRegular Language
(0 + 10
∗
)
(0
∗
10
∗
)
(0 + ε)(1 + ε)
(a + b)*
(a + b)* abb
(11)*
(aa)*(bb)*b
(aa + ab + ba+bb)*
Language of given Regular Expression?
https://www.tutorialspoint.com/automata_theory/regular_expressions.htm

4. RegularExpressionRegular Language
(0 + 10
∗
) L = { 0, 1, 10, 100, 1000, 10000, … }
(0
∗
10
∗
) L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L = {ε, 0, 1, 01}
(a + b)*
(a + b)* abb
(11)*
(aa)*(bb)*b
(aa + ab + ba+bb)*
Language of given Regular Expression?
https://www.tutorialspoint.com/automata_theory/regular_expressions.htm

5. RegularExpressionRegular Language
(0 + 10
∗
) L = { 0, 1, 10, 100, 1000, 10000, … }
(0
∗
10
∗
) L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L = {ε, 0, 1, 01}
(a + b)* Set of strings of a’s and b’s of any length including the null string. So L = { ε, a, b,
aa , ab , bb , ba, aaa…….}
(a + b)* abb Set of strings of a’s and b’s ending with the string abb. So L = {abb, aabb, babb,
aaabb, ababb, …………..}
(11)*
(aa)*(bb)*b
(aa + ab + ba+bb)*
Language of given Regular Expression?
https://www.tutorialspoint.com/automata_theory/regular_expressions.htm

6. RegularExpressionRegular Language
(0 + 10
∗
) L = { 0, 1, 10, 100, 1000, 10000, … }
(0
∗
10
∗
) L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L = {ε, 0, 1, 01}
(a + b)* Set of strings of a’s and b’s of any length including the null string. So L = { ε, a, b,
aa , ab , bb , ba, aaa…….}
(a + b)* abb Set of strings of a’s and b’s ending with the string abb. So L = {abb, aabb, babb,
aaabb, ababb, …………..}
(11)* Set consisting of even number of 1’s including empty string, So L= {ε, 11, 1111,
111111, ……….}
(aa)*(bb)*b Set of strings consisting of even number of a’s followed by odd number of b’s , so L = {b, aab, aabbb, aabbbbb, aaaab,
aaaabbb, …………..}
(aa + ab + ba+bb)*String of a’s and b’s of even length can be obtained by concatenating any
combination of the strings aa, ab, baand bb including null, so L = {aa, ab, ba, bb, aaab, aaba, ………..}
Language of given Regular Expression?
https://www.tutorialspoint.com/automata_theory/regular_expressions.htm

7. Number of states for a given language
Definition of a language L with alphabet {a} is given as following
L = {a
nk
| k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
Computer Science GATE 2011

8. Number of states for a given language
Definition of a language L with alphabet {a} is given as following
L = {a
nk
| k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
n+1states are needed in a DFA to recognize L
Let n = 3 and k=1
3+1 = 4 states
Computer Science GATE 2011

9. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0, 1} ∪{x ∈{0, 1}∗| len(x) ≥ 3}
Konrad SlindNotes on Computation Theory, September 21, 2010

10. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0, 1} ∪{x ∈{0, 1}∗| len(x) ≥ 3}
Konrad SlindNotes on Computation Theory, September 21, 2010

11. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0, 1} ∪{x ∈{0, 1}∗| len(x) ≥ 3}
Konrad SlindNotes on Computation Theory, September 21, 2010

12. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0, 1} ∪{x ∈{0, 1}∗| len(x) ≥ 3}
Konrad SlindNotes on Computation Theory, September 21, 2010

13. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0
n
| ∃k. n = 3k + 1}
Konrad SlindNotes on Computation Theory, September 21, 2010

14. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0
n
| ∃k. n = 3k + 1}
Konrad SlindNotes on Computation Theory, September 21, 2010

15. Minimal DFA for a given language
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {0, 1} is given
below {0
n
| ∃k. n = 3k + 1}
Konrad SlindNotes on Computation Theory, September 21, 2010

16. Convert NFA to DFA for a given RegEx
Construct DFA to accept 00(0+1)*
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

17. Convert NFA to DFA for a given RegEx
Construct DFA to accept 00(0+1)*
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

18. Convert NFA to DFA for a given RegEx
Construct DFA to accept (0+1)*11
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

19. Convert NFA to DFA for a given RegEx
Construct DFA to accept (0+1)*11
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

20. Convert NFA to DFA for a given RegEx
Construct DFA to accept 00(0+1)*11
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

21. Convert NFA to DFA for a given RegEx
Construct DFA to accept 00(0+1)*11
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

22. Convert NFA to DFA for a given RegLang
Construct DFA to accept L(M)=ε
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

23. Convert NFA to DFA for a given RegLang
Construct DFA to accept L(M)=ε
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

24. Convert NFA to DFA for a given RegLang
Construct DFA to accept L(M)=Ǿ
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

25. Convert NFA to DFA for a given RegLang
Construct DFA to accept L(M)=Ǿ
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

26. Convert NFA to DFA for a given RegLang
Construct DFA to acceptL(M)=(0+1)*
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

27. Convert NFA to DFA for a given RegLang
Construct DFA to accept L(M)=(0+1)*
Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt

28. Regular Expression
What is the language accepted by the NFA for one literal {a} show below?
Assume ε is the empty string
Computer Science GATE 2012

29. Regular Expression
What is the language accepted by the NFA for one literal {a} show below?
Assume ε is the empty string
Language accepted by NFA is a+, so complement of this language is {є}
Computer Science GATE 2012

30. What is theDFA & Regularexpression?
30Lexical Analysis by Prof. O. Nierstrasz
Example:the set of strings containing an even number of zeros and an even number of ones

31. What is theDFA & Regularexpression?
31Lexical Analysis by Prof. O. Nierstrasz
Example:the set of strings containing an even number of zeros and an even number of ones

32. What is the DFA & Regular expression?
32Lexical Analysis by Prof. O. Nierstrasz
Example:the set of strings containing an even number of zeros and an even number of ones
The RE is (0011)*((0110)(0011)*(0110)(0011)*)*

33. Draw NFA for givenregularexpressions
33Lexical Analysis by Prof. O. Nierstrasz
For the RE (a|b)*abb?

34. Draw NFA for given regular expressions
34Lexical Analysis by Prof. O. Nierstrasz
For the RE (a|b)*abb?

35. Draw NFA for given regular expressions
35
For the RE (a|b)*abb?
State s
0has multiple transitions on a! It is a non-deterministicfiniteautomaton
Lexical Analysis by Prof. O. Nierstrasz

36. 36
A language is regular if it is recognized by
a deterministic finite automaton
Whether L = { w | w contains 001} is regular or not?
Check it by building an automaton accepts all and only those strings that contain 001
Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789

37. 37
q q
00
1 0
1
q
0 q
001
0
0 1
0,1
A language is regular if it is recognized by
a deterministic finite automaton
Whether L = { w | w contains 001} is regular or not?
Check it by building an automaton accepts all and only those strings that contain 001
Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789

38. A language is regular if it is recognized by
a deterministic finite automaton
Whether L = { w | w has an even number of 1s} is regular or not?
Check it by building an automaton accepts all and only those strings that has an even number
of 1s
Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789

39. A language is regular if it is recognized by
a deterministic finite automaton
q
0
q
1
0
0
1
1
Whether L = { w | w has an even number of 1s} is regular or not?
Check it by building an automaton accepts all and only those strings that has an even number
of 1s
Steven Rudich: www.cs.cmu.edu/~rudich rudich0123456789

40. References
https://www.tutorialspoint.com/automata_theory/regular_expressions.htm
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University
http://www.cs.tau.ac.il/~orilahav/CompModelFall10/Compute2-print.pdf
Slide by: Dr. Harry H. Porter http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart3.pdf
Slide by Dr. Ding-Zhu Du http://www.utdallas.edu/~dzdu/cs4384/lect7.ppt
Prof. Shunichi Toidahttp://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-2-dfa.html
Konrad SlindNotes on Computation Theory, September 21, 2010
Lexical Analysis by Prof. O. Nierstrasz
GATE (Graduate Aptitude Test of Engineering) jointly conducted by IIT’s