Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    TOA Lecture06

    Uploaded by

    Hamza Anjum
    Theory of automata lecture slide

    Copyright:

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

    TOA Lecture06

    Uploaded by

    Hamza Anjum
    1 views18 pages
    Theory of automata lecture slide

    Original Title

    TOA-Lecture06

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Theory of automata lecture slide

    Copyright:

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

    TOA Lecture06

    Uploaded by

    Hamza Anjum
    Theory of automata lecture slide

    Copyright:

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

    Lecture No 6

    Transition Graph

    Dr. Nazir Ahmad Zafar 1


    1. Transition Graph
    1. Transition graph (TG)
    2. Finding all possible paths for checking acceptance
    of a string using TG
    3. Generalized TG

    Dr. Nazir Ahmad Zafar 2


    1. Transition Graph
    Definition:
    A Transition graph (TG), is a collection of the
    followings:
    1. Finite number of states, at least one of which is start
    state and some (may be none) final states.
    2. Finite set of input letters (Σ) from which input
    strings are formed.
    3. Finite set of transitions that show how to go from
    one state to another based on reading specified
    substrings of input letters, possibly even the null
    string (Λ). Dr. Nazir Ahmad Zafar 3
    1. Transition Graph
    Example: Σ = {a, b}
    Consider the Languages L ,
    “all strings including Λ”
    a,b a,b
    Λ +
    –

    a,b a,b
    a, b +
    + +

    Dr. Nazir Ahmad Zafar 4


    1. Transition Graph
    Example: Σ = {a, b}
    Consider the following TG’s
    TG1: TG2: TG3:
    a,b
    - - a, b a, b
    1 - 1

    What language is accepted by TG1 & TG2 & TG3?


    Which one is the F.A also?
    Note:
    Every FA is a TG but converse may not be true i.e.
    every TG may not be an FA.
    Dr. Nazir Ahmad Zafar 5
    1. Transition Graph
    Example: Σ = {a, b}
    Consider the language L of strings,
    “starting with b”. a,b
    b
    RE = b(a + b)* - +

    Can you draw


    an equivalent FA ?
    a,b
    Example 2 a
    – +
    “not ending in b” Λ
    RE = Λ + (a + b)*a
    Dr. Nazir Ahmad Zafar + 6
    1. Transition Graph
    Example: Σ = {a, b}
    Consider the language L of strings,
    “containing double a ”. b,a b,a
    RE = (a+b)* (aa) (a+b)*. 1-
    aa
    2+

    “having double a or double b ” x


    RE = (a+b)* (aa + bb) (a+b)*. a a
    a,b a,b
    – +
    Any difference b/w
    b b
    TG & FA you feel here?
    Dr. Nazir Ahmad Zafar y 7
    1. Transition Graph
    Example: Σ = {a, b}
    RE = (a+b)* (aa + bb) (a+b)*. a,b a,b
    aa
    a,b a,b 1- 2+
    - aa,bb
    +
    OR a,b a,b
    3- bb 4+

    Note
    In the above TG if the states are not labeled then
    it may not be considered to be a single TG
    Dr. Nazir Ahmad Zafar 8
    1. Transition Graph
    Example: Σ = {a, b}
    Consider the language L of strings,
    “having triple a or triple b”
    RE = (a+b)* (aaa + bbb) (a+b)*

    “beginning and ending in different letters”


    RE = a(a + b)*b + b(a + b)*a

    Dr. Nazir Ahmad Zafar 9


    1. Transition Graph
    Example: Σ = {a, b}
    Consider the language L of strings, “of length two or
    more beginning with and ending in same letters”.
    RE = a(a + b)*a + b(a + b)*b

    Consider the EVEN-EVEN language


    RE = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

    Dr. Nazir Ahmad Zafar 10


    1. Transition Graph
    Example: Σ = {a, b}
    Consider the language L of strings in which
    “a’s occur only in even clumps and that
    ends in three or more b’s. ”.
    RE = (aa)*b(b*+(aa(aa)*b)*) bb OR
    (aa)*b(b*+( (aa)+b)*) bb.

    Dr. Nazir Ahmad Zafar 11


    2. All possible paths for string acceptance

    Example:
    Σ = {a, b}
    Consider the TG

    Does string “abbbabbbabba” is accepted by TG?


    In how many ways & indicate the paths ?
    Successful sequence of states: -444+3221+
    Dr. Nazir Ahmad Zafar 12
    3. Generalized Transition Graph
    (GTG)

    Dr. Nazir Ahmad Zafar 13


    3. Generalized Transition Graph (GTG)
    A Generalized Transition Graph (GTG) is a
    collection of three things:
    1. Finite number of states, at least one of which is start
    state and some (maybe none) final states.
    2. Finite set of input letters (Σ) from which input
    strings are formed.
    3. Directed edges connecting some pair of states
    labeled with regular expression.
    It may be noted that in GTG, the labels of transition
    edges are corresponding regular expressions
    Dr. Nazir Ahmad Zafar 14
    3. Generalized Transition Graph (GTG)

    Example Σ = {a,b}
    Consider the language L of strings containing
    “double a or double b”
    R.E = (a+b)* (aa + bb) (a+b)*

    Dr. Nazir Ahmad Zafar 15


    3. Generalized Transition Graph (GTG)
    Example Σ = {a,b}
    Consider the language L of strings of beginning
    with and ending in same letters
    R.E = (a + b) + a(a + b)*a + b(a + b)*b

    Dr. Nazir Ahmad Zafar 16


    3. Generalized Transition Graph (GTG)

    Example Σ = {a,b}
    Consider the language L of strings of “beginning
    and ending in different letters”
    R.E = a(a + b)*b + b(a + b)*a

    OR

    Dr. Nazir Ahmad Zafar 17


    3. Generalized Transition Graph (GTG)

    Example Σ = {a,b}
    Consider the language L of strings of
    “having triple a or triple b ”
    R.E = (a+b)* (aaa + bbb) (a+b)*

    Dr. Nazir Ahmad Zafar 18

    You might also like