Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    Lesson 06

    Uploaded by

    zeeshanfarewd

    Copyright:

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

    Lesson 06

    Uploaded by

    zeeshanfarewd
    7 views23 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Lesson 06

    Uploaded by

    zeeshanfarewd

    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 23

    Recap lecture 5

     Different notations of transition diagrams,


    languages of strings of even length, Odd
    length, starting with b, ending in a
    (with different FAs), beginning with
    a, not beginning with b, beginning
    with and ending in same letters

    1
    TASK

    Build an FA for the language L of


    strings, defined over Σ={a, b}, of
    odd length.
    Solution:The language L may be
    expressed by RE
    (a+b)((a+b)(a+b))* or
    ((a+b)(a+b))*(a+b)
    This language may be accepted by
    the following FA
    2
    Solution continued …

    a,b

    1 – 2+

    a,b

    3
    Task
     Build an FA accepting the Language L of
    Strings, defined over Σ = {a, b}, beginning
    with and ending in same letters.
    Solution:The language L may be expressed
    by the following regular expression
    (a+b)+a(a + b)*a + b(a + b)*b
    This language L may be accepted by the
    following FA

    4
    Solution continued …

    a b a
    a
    b
    a
    2+ 4 6+
    b
    1– b a b
    b
    b
    a
    3+ 5 7+
    a

    5
    Example

    Consider the Language L of Strings ,


    defined over Σ = {a, b}, beginning with
    and ending in different letters.
    The language L may be expressed by the
    following regular expression
    a (a + b)* b + b (a + b)* a
    This language may be accepted by the
    following FA

    6
    Example Continued …

    a b b

    2 4+
    a a
    1–
    b a
    a
    b
    3 5+
    b

    7
    Example

     Consider the Language L , defined over


    Σ = {a, b} of all strings including Λ,
    The language L may be accepted by the
    following FA a,b

    a,b

    1 2+

     The language L may also be accepted by


    the following FA
    8
    Example Continued …
    a,b

     The language L may be expressed by the


    following regular expression

    (a + b)*

    9
    Example

     Consider the Language L , defined over Σ=


    {a, b} of all non empty strings. The language
    L may be accepted by the following FA

    a,b

    a,b
    – +
    The above language may be expressed by the
    following regular expression (a + b)+

    10
    Example

     Consider the following FA, defined over Σ


    = {a, b}
    a,b
    a,b
    – +

     It is to be noted that the above FA does not


    accept any string. Even it does not accept
    the null string. As there is no path starting
    from initial state and ending in final state.
    11
    Equivalent FAs

    It is to be noted that two FAs are said


    to be equivalent, if they accept the
    same language, as shown in the
    following FAs.

    12
    Equivalent FAs Continued …
    a,b
    FA1 –
    a,b
    +
    a,b

    FA2 a,b
    1 – 2

    a,b a,b

    a,b
    FA3 1– 2 3
    +

    13
    Note (Equivalent FAs)

     FA1 has already been discussed, while in


    FA2, there is no final state and in FA3, there
    is a final state but FA3 is disconnected as
    the states 2 and 3 are disconnected.
    It may also be noted that the language of
    strings accepted by FA1, FA2 and FA3 is
    denoted by the empty set i.e.
    { } OR Ø

    14
    Example

    Consider the Language L of strings ,


    defined over Σ = {a, b}, containing
    double a.
    The language L may be expressed by
    the following regular expression
    (a+b)* (aa) (a+b)*.
    This language may be accepted by
    the following FA

    15
    Example Continued …

    b a,b
    a
    a
    1- 2 3+
    b

    16
    Example
    Consider the language L of strings, defined
    over
    Σ={0, 1}, having double 0’s or double 1’s,
    The language L may be expressed by the
    regular expression (0+1)*
    (00 + 11) (0+1)*
    This language may be accepted by the
    following FA

    17
    Example Continued …

    0 0
    0,1

    - 0 1 +

    1
    1

    y
    18
    Example

    Consider the language L of strings,


    defined over Σ={a, b}, having triple a’s
    or triple b’s. The language L may be
    expressed by RE
    (a+b)* (aaa + bbb) (a+b)*
    This language may be accepted by the
    following FA

    19
    Example Continued …
    2 a
    4

    a
    a
    b a,b

    1–– a b 6+

    b a
    b

    3 b 5
    20
    Example

     Consider the EVEN-EVEN language,


    defined over Σ={a, b}. As discussed
    earlier that EVEN-EVEN language can
    be expressed by the regular expression
    (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
    EVEN-EVEN language may be accepted
    by the following FA

    21
    Example Continued …

    1 3
    b

    a a a a

    2 4
    b

    22
    Summing Up

     Language of strings beginning with


    and ending in different letters,
    Accepting all strings, accepting non-
    empty strings, accepting no string,
    containing double a’s, having double
    0’s or double 1’s, containing triple a’s
    or triple b’s, EVEN-EVEN

    23

    You might also like