Regular Expressions

Regular Expressions

Recap: Transformation NFA DFA si s1 e e e s2

pi ... >s s p1 p2 > s1

... sn p1 p2 ... pm Closure Under Set Operations Theorem. Let L and M two regular languages, then the

following languages are also regular: LM LC LM LM LM L* Regular Expressions A regular expression is defined inductively over the alphabet { (, ), e, , , *} as follows: , e, and each character in are regular expressions (step 0) If and are regular expressions then:

( ) () * are also regular expressions (inductive step) No other string over the alphabet { (, ), e, , , *} is a regular expression + k Language Representing Regular Expressions We define a mapping from a regular expression to a language L() as follows:

Step 0: L() = {} L(e) = {e} L() ={} for each Inductive step: L(( )) = L() L() L(()) = L()L() L(*) = L()* Example (1) Example 1. Find L((ab*)a) L(ab*a) = L(a)L(b)*L(a) = {w : w is of the form abna with n = 0, 1, 2,}

Example 2. Find L((a(a b)*)). L(a(a b)*) = L(a)(L(a) L(b))* = {aw : w is a word in } Example (2) Find the regular expression for the language L in the alphabet {a,b} such that the words in L contains the substring aaa Find the regular expression for the language L in the alphabet {a,b} such that the words in L contains the substring aaa or bbb Main Theorem About Finite Automata (Kleene) (1) Given a finite automata A, there is a regular expression

expr such that L(A) = L(expr) (2) Given a regular expression expr, there is a finite automata A such that L(A) = L(expr) Regular languages regular expressions Theorem 1.54 Input: a regular expression expr Output: a finite automaton accepting L(expr) 1. Convert any step-0 element (any of the characters in , or e) occurring in expr to a finite automaton accepting this element

2. Apply the theorem about closure under set operations to every Union Concatenation Kleene star Example Obtain a finite automaton accepting the regular expression: ((a ab)*ba)*. The impact of this Algorithm is a dream (or a nightmare?)

of programmers: given the specification of a language there is an algorithm that recognizes it automatically. Example: Yak and Lex tools in Unix. Lemma 1.60 Input: a finite automaton A Output: a regular expression expr such that L(expr) = L(A) Assumptions about the automaton A: A has a single favorable state There are no transitions directed to the initial state There are no transitions starting at the favorable state Nodes will be labeled 1, 2, , n, where 1 is the initial state and n is the favorable state Definition. An generalized NFA is am NFA in which the

arrows are labeled by regular expressions. (Unlike regular NFAs in which transitions are only labeled by characters in ) Construction (1) for every pair of nodes such that there is more than one transition from one to the other one: expr1 expr2 exprn expr1 expr2 exprn

Construction (2) for every pair of nodes such that there is an intermediate node connecting them: expr3 expr1 expr2 expr1 (expr2)* expr3 Example a a

>s b b q b r b Homework Friday Sep. 21

1.12 1.21 (a) 1.28 (c) 1.43 (either picture and an accompanying explanation or formal proof are fine) 1.60 (either state diagram or formal definition are fine)

Recently Viewed Presentations

  • + Monitoring Access Tools and Accommodations in a

    + Monitoring Access Tools and Accommodations in a

    Accoms must be available - however, this does not mean a student MUST use them. our current system has no way of tracking if a student uses or not - and this will be addressed later in presentation. Show next...
  • Brand and Marketing Communication

    Brand and Marketing Communication

    Brand Value Chain. Getting beyond traditional measures to ROMI requires…. Understanding of entire sales and service cycle - not just communications. A multi-channel view of the organization. ... Brand and Marketing Communication Last modified by:
  • Othello - Weebly

    Othello - Weebly

    His failure to attend would be interpreted as a grave insult to the new king and so he puts principles before personal advancement. ACT TWO: REVISION QUIZ www.kahoot.it ACT TWO QUESTIONS In Act Two Scene I, do you think the...
  • Security Convergence andSecurity SDLC

    Security Convergence andSecurity SDLC

    The security solutions are acquired, tested, implemented, and tested again ... Maintenance Model. While a systems management model is designed to manage and operate systems, a maintenance model is intended to focus organizational effort on system maintenance:
  • Identifying the Elements of A Plot Diagram

    Identifying the Elements of A Plot Diagram

    Arial MS Pゴシック Calibri Arial Black Default Design Identifying the Elements of Plot (via Diagram) Today Plot Diagram Plot (definition) Hook 1. Exposition Beauty and the Beast 2. Rising Action Rocky 3. Climax Armageddon 4. Falling Action Saints and Soldiers...
  • The AMBER study Abdominal Massage for Neurogenic Bowel

    The AMBER study Abdominal Massage for Neurogenic Bowel

    9 months left for recruitment and results of the trial will be published in summer 2017. ... Bakke A, Myhr(2007) Prevalence of bladder, bowel and sexual problems among multiple sclerosis patients two to five years after diagnosis. Multiple Sclerosis. 13:106-112.
  • Creating Vector Graphics - Duquesne Media

    Creating Vector Graphics - Duquesne Media

    Begin with selecting the Rounded Rectangle tool from the Toolbar. Remember - The Shapes are all collected as a group of tools, you may have to hold and select the Rounded Rectangle tool. Use either the Toolbar or the Property...
  • Earnings, Productivity, and the Job Market (15th ed.)

    Earnings, Productivity, and the Job Market (15th ed.)

    Earnings, Productivity, and the Job Market. Click to edit Master title style. To Accompany: "Economics: Private and Public Choice, 15th ed." James Gwartney, Richard Stroup, Russell Sobel, & David Macpherson