WELCOME TO A JOURNEY TO CS419 Dr. Hussien Sharaf Computer Science Department dr.sharaf@from-masr.com
DEFINITION OF A LANAGUAGE “L” ∑ is the set of alphabets * 1. Let ∑ ={x}, Then L = ∑ * In RE, we write x * 2. Let ∑ ={x, y}, Then L = ∑ * In RE, we write (x+y) 3. Kleene’s star “*” means any combination of letters of length zero or more. Note: Please study the appendix at the end of the lecture Dr. Hussien M. Sharaf 2
RE RULES Given an alphabet ∑, the set of regular expressions is defined by the following rules. 1. 2. For every letter in ∑, the letter written in bold is a regular expression. Λ- lamda or ε-epsilon is a regular expression. Λ or ε means an empty letter. If r1 and r2 are regular expressions, then so are: 1. 2. 3. 4. (r1) r1 r2 r1+r2 r1* and also r2* NOTE 1: r1+ is not a RE NOTE 2: spaces are ignored as long as they are not included in ∑ 3. Nothing else is a regular expression. Dr. Hussien M. Sharaf 3
RE-10.1 Example ∑ ={a, b}, What does L describe? * * - L = (a+b) a(a+b) Any string of a's and b's Any string of a's and b's Single a - Give examples for words in L {a ab aab bab abb …..} Dr. Hussien M. Sharaf 4
RE-10.2 abbaab can be parsed in 3 ways a bbaab Λ a bbaab Dr. Hussien M. Sharaf abba a b abb a ab abb a ab abba a b 5
RE-11 Example ∑ ={a, b} - Formally describe all words with at least two a's. 1) L = b*ab*a(a + b)* Start with a jungle of b's (or no b's) until we find the first a, then more b's (or no b's), then the second a, then we finish up with anything. - Give examples for words in L {abbbabb aaaaa bbbabbbbabab…..} Dr. Hussien M. Sharaf 6
RE-12 Example ∑ ={a, b} - Formally describe all words with exactly two a's. 1) L = b*ab*ab* - Give examples for words in L {aab, baba, and bbbabbbab …..} To make the word aab, we let the first and second b* become Λ and the last becomes b Dr. Hussien M. Sharaf 7
RE-13.1 Example ∑ ={a, b} - Formally describe all words with at least one a and at least one b. 1) L = (a + b)*a(a + b)* b(a + b)* = (anything) a(anything) b(anything) But (a+b)*a(a+b)*b(a+b)* expresses all words except words of the form some b’s (at least one) followed by some a’s (at least one). bb*aa* Dr. Hussien M. Sharaf 8
RE-13.1 2) L =(a+b)*a(a+b)*b(a+b)* + bb*aa* Thus: (a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)* = (a+b)*a(a+b)*b(a+b)* + bb*aa* Notice that it is necessary to write bb*aa* because b*a* will admit words we do not want, such as aaa. Does this imply that (a+b)*b(a+b)*a(a+b)*= bb*aa*?? False Left side includes the word aba, which the expression on the right side does not. Dr. Hussien M. Sharaf 9
ASSIGNMENTS 1. 2. 3. [One week] Solve Compilers-Sheet_0General.pdf [One week] Solve Compilers_Sheet_1_RE.pdf [Two weeks] Implement an email validator using Python. a. b. c. Build a GUI using python Tkinter. The GUI must include at least two labels, a TextBox and a Button. The user is given a message on a label stating whether the email is a valid email or not. Dr. Hussien M. Sharaf 10
DEADLINE Thursday 28th of Feb is the deadline. No excuses. Don’t wait until last day. TAs can help you to the highest limit within the next 3 days. Dr. Hussien M. Sharaf 11
THANKS Dr. Hussien M. Sharaf 12
Learning a Lexical Simplifier Using Wikipedia Colby Horn, Cathryn Manduca, David ...
Read more
Slide 1 1 Lexical Analysis Slide 2 2 Contents Introduction to lexical analyzer Tokens Regular expressions ... (RE) Finite automata ...
Read more
... (adsense.get_banner_code('200x90')); Slide 1 Using key-word analysis to create LSP materials: ... identifying lexical layers Mike Nelson 20.3.2012 ...
Read more
PowerPoint Presentation Foundation year Lec.4: Word Processing Software Using Microsoft Office 2007 Computer For Health Sciences COMP101 Lecturer: Dalia ...
Read more
Add a comment