Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    Lecture 4

    Uploaded by

    kamee tayis
    This document summarizes key concepts from Lecture 4 including regular expressions for EVEN-EVEN languages, differences between a* + b* and (a+b)*, and introduction to finite automata including definition, transition tables, diagrams, and examples of automata for languages of even length, odd length, starting or ending with certain letters, and beginning and ending with the same letter. Examples are provided to demonstrate representation of languages using regular expressions and finite automata.

    Copyright:

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

    Lecture 4

    Uploaded by

    kamee tayis
    29 views20 pages
    This document summarizes key concepts from Lecture 4 including regular expressions for EVEN-EVEN languages, differences between a* + b* and (a+b)*, and introduction to finite automata including definition, transition tables, diagrams, and examples of automata for languages of even length, odd length, starting or ending with certain letters, and beginning and ending with the same letter. Examples are provided to demonstrate representation of languages using regular expressions and finite automata.

    Original Description:

    need

    Original Title

    lecture 4

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document summarizes key concepts from Lecture 4 including regular expressions for EVEN-EVEN languages, differences between a* + b* and (a+b)*, and introduction to finite automata including definition, transition tables, diagrams, and examples of automata for languages of even length, odd length, starting or ending with certain letters, and beginning and ending with the same letter. Examples are provided to demonstrate representation of languages using regular expressions and finite automata.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    29 views20 pages

    Lecture 4

    Uploaded by

    kamee tayis
    This document summarizes key concepts from Lecture 4 including regular expressions for EVEN-EVEN languages, differences between a* + b* and (a+b)*, and introduction to finite automata including definition, transition tables, diagrams, and examples of automata for languages of even length, odd length, starting or ending with certain letters, and beginning and ending with the same letter. Examples are provided to demonstrate representation of languages using regular expressions and finite automata.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 20

    Recap Lecture 4

    Regular expression of EVEN-EVEN language,


    Difference between a* + b* and (a+b)*,
    Equivalent regular expressions; sum, product
    and closure of regular expressions; regular
    languages, finite languages are regular,
    introduction to finite automaton, definition of
    FA, transition table, transition diagram.

    1
    Note

    It may be noted that to indicate the initial state,


    an arrow head can also be placed before that
    state and that the final state with double circle,
    as shown below. It is also to be noted that while
    expressing an FA by its transition diagram, the
    labels of states are not necessary.
    a, b

    a, b

    2
    Example

    Σ = {a,b}
    States: x, y, where x is both initial and final
    state.
    Transitions:
    1.At state x reading a or b go to state y.
    2.At state y reading a or b go to state x.

    3
    Example Continued …

    These transitions can be expressed by the


    following transition table

    Old States New States


    Reading Reading
    a b
    x± y y

    y x x

    4
    Example Continued …

    It may be noted that the previous transition


    table may be depicted by the following
    transition diagram.

    a, b

    x y

    a, b

    5
    Example Continued …

    The previous transition diagram is an FA


    accepting the language of strings, defined over
    Σ={a, b} of even length. It may be noted
    that this language may be expressed by the
    regular expression

    ((a+ b) (a + b))*

    6
    TASK

    Build an FA for the language L of strings,


    defined over Σ={a, b}, of odd length.

    7
    Solution of Task

    a,b

    – +

    a,b

    8
    Example: Consider the language L of strings,
    defined over Σ={a, b}, starting with b. The
    language L may be expressed by RE b(a + b)* ,
    may be accepted by the following FA
    a,b

    ––
    b +

    a,b
    a

    1
    9
    Example:
    Consider the language L of strings, defined
    over Σ={a, b}, ending in a. The language L
    may be expressed by RE
    (a+b)*a
    This language may be accepted by the following
    FA

    10
    Example Continued …

    b a a

    – +

    There may be another FA corresponding to the


    given language.
    11
    Example continued …

    a
    a +
    ––

    a b
    b

    12
    Note

    It may be noted that corresponding to a given


    language there may be more than one FA
    accepting that language, but for a given FA
    there is a unique language accepted by that FA.

    13
    Note

    It is to be noted that given the languages L1 and


    L2 ,where
    L1 = The language of strings, defined over
    Σ={a, b}, beginning with a
    L2 = The language of strings, defined over
    Σ={a, b}, not beginning with b
    The  does not belong to L1 while it does belong
    to L2 . This fact may be depicted by the
    corresponding transition diagrams of L1 and L2.

    14
    FA1 Corresponding to L1
    a,b

    ––
    a +

    b a,b

    The language L1 may be expressed by the


    regular expression a(a + b)*
    15
    FA2 Corresponding to L2
    a,b

    a
     +

    a,b
    b

    The language L2 may be expressed by the


    regular expression a (a + b)* + Λ

    16
    Example
    Consider the Language L of Strings of length
    two or more, defined over Σ = {a, b},
    beginning with and ending in same letters.
    The language L may be expressed by the
    following regular expression
    a (a + b)* a + b (a + b)* b
    It is to be noted that if the condition on the
    length of string is not imposed in the above
    language then the strings a and b will then
    belong to the language.
    This language L may be accepted by the
    following FA 17
    Example Continued …

    b a a

    +
    a b
    –
    a b
    b
    b
    +
    a

    18
    Task

    Build an FA accepting the Language L of Strings,


    defined over Σ = {a, b}, beginning with and
    ending in same letters.

    19
    Summing Up

    Different notations of transition diagrams,


    languages of strings of even length, Odd
    length, starting with b, ending in a,
    beginning with b, not beginning with b,
    beginning and ending in same letters;

    20

    You might also like