Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Compiler

    Uploaded by

    Priyanka Manna
    This document discusses regular expressions and how to convert them to non-deterministic finite automata (NFAs). It begins with an introduction to regular expressions and regular languages. It then covers languages associated with regular expressions, identities for regular expressions, properties of regular expressions, and Arden's theorem. The document concludes by explaining how to systematically convert a regular expression into an equivalent NFA using a step-by-step process with examples.

    Copyright:

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

    Compiler

    Uploaded by

    Priyanka Manna
    9 views10 pages
    This document discusses regular expressions and how to convert them to non-deterministic finite automata (NFAs). It begins with an introduction to regular expressions and regular languages. It then covers languages associated with regular expressions, identities for regular expressions, properties of regular expressions, and Arden's theorem. The document concludes by explaining how to systematically convert a regular expression into an equivalent NFA using a step-by-step process with examples.

    Original Description:

    Original Title

    compiler

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses regular expressions and how to convert them to non-deterministic finite automata (NFAs). It begins with an introduction to regular expressions and regular languages. It then covers languages associated with regular expressions, identities for regular expressions, properties of regular expressions, and Arden's theorem. The document concludes by explaining how to systematically convert a regular expression into an equivalent NFA using a step-by-step process with examples.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    9 views10 pages

    Compiler

    Uploaded by

    Priyanka Manna
    This document discusses regular expressions and how to convert them to non-deterministic finite automata (NFAs). It begins with an introduction to regular expressions and regular languages. It then covers languages associated with regular expressions, identities for regular expressions, properties of regular expressions, and Arden's theorem. The document concludes by explaining how to systematically convert a regular expression into an equivalent NFA using a step-by-step process with examples.

    Copyright:

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

    a presention on regular expression and regular expression to nfa

    name:priyanka manna
    roll no:12000121056
    PAPER NAME : compiler design
    paper code : pcc-cs 501
    SEMESTER: 5th sem

    dr. b. c roy engineering college, Durgapur-713206


    department of computer science & engineering
    (affiliated to maulana abul kalam azad university of technology )
    • Introduction
    • Languages associated with Regular
    agenda Expression
    • Identities for Regular Expression
    • Properties of Regular Expression
    • Arden’s Theorem
    • Conversion of Regular expression
    to NFA
    • Conclusion
    INTRODUCTION
     The language accepted by finite automata can be easily described by simple
    expressions called Regular Expressions. It is combination of dot(.),star(*),parenthesis
    and plus(+).
     The languages accepted by some regular expression are referred to as Regular
    languages.
     A regular expression can also be described as a sequence of pattern that defines a
    string.
     Regular expressions are used to match character combinations in strings. String
    searching algorithm used this pattern to find the operations on a string.
     Let Σ be a given alphabets then φ, λ, a∈ Σ are all regular expressions.These are called
    primitive regular expression.
     If r1 and r2 are all regular expression then r1+r2, r1r2, r1* and(r1) are also regular
    expression.
    LANGUAGE ASSOCIATED WITH REGULAR EXPRESSION
    Let r be regular expression then L(r) denoted by language associated with regular expression.
    It is defined by the following rules
    •Φ is regular expression ,denoting the empty set.
    •λ is a regular expression, denoting { λ }.
    •For every a∈ Σ ,a is a regular expression ,denoting { a }.
    •If r1 and r2 are regular expression then L(r1 + r2)= L(r1) + L(r2).
    •L(r1.r2) = L(r1).L(r2)
    •L((r1)) = L(r1)
    •L(r1*) = (L(r1))*

    identities of REGULAR EXPRESSION


    Let P,R,Q are regular expression then identities rule are
     εR=R
     ε*= ε Where, ε is null string
     (Φ)*= ε Where,Φ is empty string
     Φ.R=R.Φ= Φ
     Φ+R = R
     R+R = R
     RR* = R*R = R+
     (R*)* = R*
     ε + RR* = R*
     (P+Q)R = PR+QR
     (P+Q)*= (P*Q*)* = (P*+Q*)*
     R*(ε+R)=( ε+R)R*= R*
     (R+ε)*= R*

    ARDEN’S THEOREM
    Let P and Q be two regular expression.P does not contain λ then the following equation
    in R that is R= Q + RP has a unique solution given by R = QP*
    PROPERTIES FOR REGULAR EXPRESSION
    Union:
    Let L and M be the languages of regular expressions R and S, respectively.Then R+S is a
    regular expression whose language is(L U M).
    Intersection:
    Let L and M be the languages of regular expressions R and S, respectively then it is a regular
    expression whose language is (L ∩ M).
    Kleene Closure:
    R, S is a regular expression whose language is L, M. R* is a regular expression whose
    language is L*.
    Positive Closure:
    R,S is a regular expression whose language is L, M.R+ is a regular expression whose language
    is L+.
    Complement:
    The complement of regular expression is also regular expression.
    REGULAR EXPRESSION to nfa
    An NDFA is represented by digraphs called state diagram
    •The vertices represent the states.
    • The arcs labeled with an input alphabet show the transitions.
    • The initial state is denoted by an empty single incoming arc.
    • The final state is indicated by double circles.
    Example:1
    Design a NFA from given regular expression (ab)*ab*
    Step 1:
    ab b
    q0 a qf
    Step 2:
    q1
    a b
    b
    q0 a qf

    Example:2
    Design a NFA from given regular expression (a+ba)*ba
    Step 1:
    a+ba
    b a
    q0 q1 qf
    Step 2:
    a
    b a qf
    q0 q1
    ba
    Step 3:

    a
    q0 b a qf
    q1
    a
    b
    q2
    conclusion
    Regular expressions are a compact textual representation of a set of
    strings representing a language.Regular expressions appeared as
    Type-3 languages in Chomsky’s hierarchy.The class of regular
    languages is a proper subset of the context-free languages.Any
    Regular expression can be automatically compiled into an NFA,to a
    DFA, and to a unique minimum-state DFA.

    You might also like