際際滷

際際滷Share a Scribd company logo

Kleene's theorem

Download as PPT, PDF
S
Samita Mukesh

This document contains information about converting regular expressions to finite automata. It discusses Kleene's theorem, which states that any language that can be defined by a regular expression can also be defined by a finite automaton and vice versa. It then provides steps for converting a regular expression to an NFA- and converting an NFA- to a finite automaton. The document concludes by recommending reviewing a textbook chapter on these topics.

1 of 18
Downloaded 145 times
COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969 WARNING This material has been reproduced and communicated to you by or on behalf of Monash University pursuant to Part VB of the Copyright Act 1968 (the Act). The material in this communication may be subject to copyright under the Act. Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act. Do not remove this notice.
Converting Regular ExpressionsConverting Regular Expressions into Finite Automatainto Finite Automata CSE2303 Formal Methods I Lecture 5
OverviewOverview Questions Kleenes Theorem Consequences Convert Regular Expressions to NFA- Convert NFA- to FA
QuestionsQuestions Can every language which is represented by a regular expression be described by a finite automaton? Can every language which is described by a finite automaton be represented by a regular expression? Can every language be represented by a regular expression or a finite automaton?
Kleenes TheoremKleenes Theorem Any language which can be defined by Regular Expressions Finite Automaton Nondeterministic Finite Automaton (NFA) NFA- Transition Graphs Generalised Transistion Graphs can be defined by any of the other methods
The Complement of RegularThe Complement of Regular Language is a Regular LanguageLanguage is a Regular Language Outline of Proof: Suppose we have a Regular Language. Therefore we have a regular expression that defines the language. So, by Kleenes Theorem, there is a FA that defines this language. We can convert this FA into one that defines the complement the language. So, by Kleenes Theorem, there is a regular expression that defines the complement.
Kleenes TheoremKleenes Theorem Regular Expression Finite Automaton NFA-GTG TG NFA
How to convert aHow to convert a Regular ExpressionRegular Expression into ainto a NFA-NFA-
Converting Regular ExpressionConverting Regular Expression to NFA-to NFA- Start with the graph. - + Regular Expression
Apply the following rules until all edges are labeled with a letter or . 1. Delete any edge labeled with . 2. Transform any edge like RS R into S
3. Transform any edge like: into R + S R S
4. Transform any edge like: into R* R
1- a b 2 3+ 4 5 6 7 a a (a* + aa*b)*(a* + aa*b)*
How to convert aHow to convert a NFA-NFA- into ainto a FAFA
a bb - a,b a,ba 3 2 41 + a b Start {1} {1,2} {1,3} {1,2} {1,2,4} {1,3} {1,3} {1,2} {1,3,4} Final {1,2,4} {1,2,4} {1,3,4} Final {1,3,4} {1,2,4} {1,3,4}
1- a b 2 3 4 5+ a b Start/Final {1,2,3,4,5} {2,3,4,5} {4,5} Final {2,3,4,5} {2,3,4,5} {4,5} Final {4,5} {4,5}
1- a b 2 3+ 4 5 6 7 a a a b Start /Final{1,2,3,4} {5,4,6,7,2,3} Final {2,3,4,5,6,7} {5,4,6,7,2,3} {2,3,4} Final {2,3,4} {5,4,6,7,2,3}
RevisionRevision Understand Kleenes Theorem Be able to convert Regular Expressions into NFA- Be able to convert NFA- into a Finite Automaton Read Text Book Chapter 8

More Related Content

Kleene's theorem

  • 1. COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969 WARNING This material has been reproduced and communicated to you by or on behalf of Monash University pursuant to Part VB of the Copyright Act 1968 (the Act). The material in this communication may be subject to copyright under the Act. Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act. Do not remove this notice.
  • 2. Converting Regular ExpressionsConverting Regular Expressions into Finite Automatainto Finite Automata CSE2303 Formal Methods I Lecture 5
  • 3. OverviewOverview Questions Kleenes Theorem Consequences Convert Regular Expressions to NFA- Convert NFA- to FA
  • 4. QuestionsQuestions Can every language which is represented by a regular expression be described by a finite automaton? Can every language which is described by a finite automaton be represented by a regular expression? Can every language be represented by a regular expression or a finite automaton?
  • 5. Kleenes TheoremKleenes Theorem Any language which can be defined by Regular Expressions Finite Automaton Nondeterministic Finite Automaton (NFA) NFA- Transition Graphs Generalised Transistion Graphs can be defined by any of the other methods
  • 6. The Complement of RegularThe Complement of Regular Language is a Regular LanguageLanguage is a Regular Language Outline of Proof: Suppose we have a Regular Language. Therefore we have a regular expression that defines the language. So, by Kleenes Theorem, there is a FA that defines this language. We can convert this FA into one that defines the complement the language. So, by Kleenes Theorem, there is a regular expression that defines the complement.
  • 7. Kleenes TheoremKleenes Theorem Regular Expression Finite Automaton NFA-GTG TG NFA
  • 8. How to convert aHow to convert a Regular ExpressionRegular Expression into ainto a NFA-NFA-
  • 9. Converting Regular ExpressionConverting Regular Expression to NFA-to NFA- Start with the graph. - + Regular Expression
  • 10. Apply the following rules until all edges are labeled with a letter or . 1. Delete any edge labeled with . 2. Transform any edge like RS R into S
  • 11. 3. Transform any edge like: into R + S R S
  • 12. 4. Transform any edge like: into R* R
  • 13. 1- a b 2 3+ 4 5 6 7 a a (a* + aa*b)*(a* + aa*b)*
  • 14. How to convert aHow to convert a NFA-NFA- into ainto a FAFA
  • 15. a bb - a,b a,ba 3 2 41 + a b Start {1} {1,2} {1,3} {1,2} {1,2,4} {1,3} {1,3} {1,2} {1,3,4} Final {1,2,4} {1,2,4} {1,3,4} Final {1,3,4} {1,2,4} {1,3,4}
  • 16. 1- a b 2 3 4 5+ a b Start/Final {1,2,3,4,5} {2,3,4,5} {4,5} Final {2,3,4,5} {2,3,4,5} {4,5} Final {4,5} {4,5}
  • 17. 1- a b 2 3+ 4 5 6 7 a a a b Start /Final{1,2,3,4} {5,4,6,7,2,3} Final {2,3,4,5,6,7} {5,4,6,7,2,3} {2,3,4} Final {2,3,4} {5,4,6,7,2,3}
  • 18. RevisionRevision Understand Kleenes Theorem Be able to convert Regular Expressions into NFA- Be able to convert NFA- into a Finite Automaton Read Text Book Chapter 8