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

Welcome to Scribd!

  • 6 views

    Quiz 2

    Uploaded by

    yimoriv309

    Copyright:

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

    Quiz 2

    Uploaded by

    yimoriv309
    6 views4 pages

    Original Title

    quiz_2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Quiz 2

    Uploaded by

    yimoriv309

    Copyright:

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

    QUIZ 02

    SCaD

    MARCH 31, 2024


    ZOHAIB ASHRAF
    521363 MORNING
    Question 1:
    Give two finite automata (DFAs and/or NFAs) that both recognize the
    regular expression (a|ab)*

    Machine #1:

    States: {q0, q1}

    Alphabet: {a, b}

    Start state: q0

    Accept states: {q0, q1}

    Transition function:

    δ(q0, a) = q0

    δ(q0, b) = q1

    δ(q1, a) = q0

    δ(q1, b) = q1
    b>
    q0 q1

    Machine #2:

    States: {q0, q1, q2}

    Alphabet: {a, b}

    Start state: q0

    Accept states: {q0, q1, q2}

    Transition function:

    δ(q0, a) = q1

    δ(q0, b) = q0

    δ(q1, a) = q2

    δ(q1, b) = q0

    δ(q2, a) = q1

    δ(q2, b) = q
    b>

    Question 2:
    Show the equivalent DFA for the above NFA:

    Closure:

    ε-closure(s1) = {s1}

    ε-closure(s2) = {s2}

    ε-closure(s3) = {s3}

    Transition Table:

    DFA state a b
    s1 s1 s1, s2, s3
    s1,s2, s3 s1, s2, s3 s1, s2, s3
    s2 s3
    s3

    Initial State:

    The initial state of the DFA is s1.

    Transitions:

    From {s1}:

    On 'a', go to {s1}.

    On 'b', go to {s1, s2, s3}.

    From {s1, s2, s3}:

    On 'a' or 'b', stay at {s1, s2, s3}.

    From {s2}:

    On 'a', go to {s3}.

    On 'b', go to ∅ .

    From {s3}:
    On 'a' or 'b', go to ∅ .

    Final States:

    {s3} is a final state, so {s1, s2, s3} is also a final state.

    Question 3:

    Consider a Flex specification with the following rules section

    a[c-f]c { std::cout « “1”;}

    a[.]c { std::cout « “2”;}

    a[cf]c+ { std::cout « “3”;}

    a.c { std::cout « “4”;}

    [ ] { std::cout « “5”;}

    . { std::cout « “6”;}

    Write the output of the generated lexer on the string

    Acadccafcc

    Solution:
    ∑ Assuming that whitespace is not significant in language:

    Then the output will be “143”

    ∑ If we assume that whitespace is significant in the language and should be tokenized separately
    Then output will be “15453”

    You might also like