Scribd Logo
Upload

Welcome to Scribd!

  • 23 views

    L11-RE Intro

    Uploaded by

    Sanket Khaire
    This document provides an overview of regular expressions and their use in describing regular languages. It defines regular expressions recursively and discusses how they can be used to represent languages. Key points covered include: - Regular expressions involve combinations of symbols, parentheses, "+", ".", and "*" to describe regular languages. - The language of a regular expression is the set of strings it represents. This is defined recursively based on the expressions' components. - Examples are given to demonstrate how regular expressions can concisely define languages and be used to simplify representations. Precedence rules for the operators are also provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    L11-RE Intro

    Uploaded by

    Sanket Khaire
    23 views17 pages
    This document provides an overview of regular expressions and their use in describing regular languages. It defines regular expressions recursively and discusses how they can be used to represent languages. Key points covered include: - Regular expressions involve combinations of symbols, parentheses, "+", ".", and "*" to describe regular languages. - The language of a regular expression is the set of strings it represents. This is defined recursively based on the expressions' components. - Examples are given to demonstrate how regular expressions can concisely define languages and be used to simplify representations. Precedence rules for the operators are also provided.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of regular expressions and their use in describing regular languages. It defines regular expressions recursively and discusses how they can be used to represent languages. Key points covered include: - Regular expressions involve combinations of symbols, parentheses, "+", ".", and "*" to describe regular languages. - The language of a regular expression is the set of strings it represents. This is defined recursively based on the expressions' components. - Examples are given to demonstrate how regular expressions can concisely define languages and be used to simplify representations. Precedence rules for the operators are also provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    23 views17 pages

    L11-RE Intro

    Uploaded by

    Sanket Khaire
    This document provides an overview of regular expressions and their use in describing regular languages. It defines regular expressions recursively and discusses how they can be used to represent languages. Key points covered include: - Regular expressions involve combinations of symbols, parentheses, "+", ".", and "*" to describe regular languages. - The language of a regular expression is the set of strings it represents. This is defined recursively based on the expressions' components. - Examples are given to demonstrate how regular expressions can concisely define languages and be used to simplify representations. Precedence rules for the operators are also provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 17

    L11- ToC

    Regular Expressions

    Course Instructors:
    Div 1: Praveen Pawar (Div 1)
    Div 2: Jibi Abraham (Div 2)

    1
    Representations of Regular Languages

    Regular Languages

    DFAs

    NFAs Regular
    ԑ-NFAs
    Expressions

    2
    Regular Expressions
     Regular expressions are another way of
    describing regular languages
     RE involves a combination of symbols from ,
    parentheses, “+” , “.”, and “*”
     Example: (a+b.c)*

     describes the language

    3
    Example
     L1 = {10, 1}, L2 = {011, 11}
     L1+L2 = {10, 1, 011, 11}
     L1L2 = {10011, 1011, 111}
     L = {10, 11}
     L* = {ԑ, 10, 11, 1010, 1111, 1011, …}

    4
    Definition of Regular Expression
     R is a regular expression if it is:
    1. a is a RE for some a ϵ , standing for the language {a}
    2. ԑ is a RE, standing for the language {ε}
    3. Ø is a RE, standing for the empty language
    4. R1+R2 is a RE, where R1 and R2 are regular expressions,
    and + signifies union
    5. R1.R2 is a RE, where R1 and R2 are regular expressions
    and this signifies concatenation (usually omitted)
    6. R* is a RE, where R is a regular expression and signifies
    closure
    7. (R) is a RE, where R is a regular expression, then a
    parenthesized R is also a regular expression
    Recursive Definition
    • Primitive regular expressions: ᵠ, ԑ, a

    • Given regular expressions r1 and r2

    Are regular expressions

    6
    Example

    A regular expression:

    Not a regular expression:

    7
    Language of RE: Definition
     For primitive regular expressions:

    8
    Definition (continued)
     For regular expressions r1 and r2

    9
    Languages of RE - Example
     L(r) : language of regular expression r
     Example:
     L(001) = {001}
     L(0+10*) = { 0, 1, 10, 100, 010, 1000, 10000,
    …}
     L((0(0+1))*) = {{0} {0,1}}*= {00, 01}* = { ε, 00,
    01, 0000, 0001, 0100, 0101, …}
     L(a*(a+b)) = {ε, a, aa, …}{a, b} = {a, b, aa, ab,
    …}
     L(aa)*(bb)*b = {a2nb2m+1: n>=0, m>=0}

    10
    Polling - 1
     What is L((0+ε)(1+ ε))?
    A. {ε, 0, 1, 01}

    B. {0, 1, 01}

    C. {ε, 0, 1, 10}

    D. None of these

    11
    Example
     What is regular expression over {a, b} for?
     Length of string exactly 2
     (a+b)(a+b)
     Length of string at least 2
     (a+b)(a+b)(a+b)*
     Length of string at most 2
     (a+b+↋)(a+b+ ↋)
     Language of even length string
     ((a+b)(a+b))*
     Language of odd string
     ((a+b)(a+b))*(a+b)
     Containing substring ab
     (a+b)*(ab)(a+b)*
    12
    Example
     String over {0, 1} with exactly a single 1
     0*10*

     All strings over {0, 1} without substring 00


     (1+01)*(0+ ↋)

    13
    RE useful for Simplification
     RØ = Ø ; concatenating the empty set to any set yields the
    empty set.

     Note that RØ will only equal R if R itself is the empty set.

     Rε = R

     Note that R+ε may or may not equal R (we are adding ε to
    the language)

     R+Ø = R
    RE Precedence
     in the order of highest precedence to lowest:
     Parentheses “()”
     Closure, “*”
     Concatenation, “.”
     Union, “+”

    15
    Polling - 2
     Is (01)*0 same as 0(10)*?
    A. Yes

    B. No

    16
    ?
    17

    You might also like