Scribd Logo
Upload

Welcome to Scribd!

  • 95 views

    TOC - Tutorial II

    Uploaded by

    Dipesh Shrestha
    1. The document discusses topics in theory of computation including designing deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs) to recognize various regular languages. 2. It also discusses converting NFAs to equivalent DFAs, minimizing DFAs, applying the pumping lemma to determine if a language is regular, and showing that regular languages are closed under union and concatenation operations. 3. Finally, it discusses constructing a finite automaton from a regular grammar that accepts the same regular language as the grammar.

    Copyright:

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

    TOC - Tutorial II

    Uploaded by

    Dipesh Shrestha
    95 views2 pages
    1. The document discusses topics in theory of computation including designing deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs) to recognize various regular languages. 2. It also discusses converting NFAs to equivalent DFAs, minimizing DFAs, applying the pumping lemma to determine if a language is regular, and showing that regular languages are closed under union and concatenation operations. 3. Finally, it discusses constructing a finite automaton from a regular grammar that accepts the same regular language as the grammar.

    Original Title

    TOC_ Tutorial II

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document discusses topics in theory of computation including designing deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs) to recognize various regular languages. 2. It also discusses converting NFAs to equivalent DFAs, minimizing DFAs, applying the pumping lemma to determine if a language is regular, and showing that regular languages are closed under union and concatenation operations. 3. Finally, it discusses constructing a finite automaton from a regular grammar that accepts the same regular language as the grammar.

    Copyright:

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

    TOC - Tutorial II

    Uploaded by

    Dipesh Shrestha
    1. The document discusses topics in theory of computation including designing deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs) to recognize various regular languages. 2. It also discusses converting NFAs to equivalent DFAs, minimizing DFAs, applying the pumping lemma to determine if a language is regular, and showing that regular languages are closed under union and concatenation operations. 3. Finally, it discusses constructing a finite automaton from a regular grammar that accepts the same regular language as the grammar.

    Copyright:

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

    Chapter 2 (Theory of Computation)

    1. Design DFA that accepts the Language, L = {w: w ϵ {a,b}* , w contains “aabab”}
    Also, Test your design for the string “aaababbb”.
    2. Design DFA for following Languages:
    a. L = {w: w ϵ {a,b}* , w contains at-least three ‘b’}
    b. L = {w: w ϵ {0,1}* , w starts with “110”}
    c. L = {w: w ϵ {0,1}* , Second symbol of w is 1 and 5th Symbol is 0}
    d. L = {w: w ϵ {a,b}* , w has even number of ‘a’ and odd number of ‘b’}
    e. L = {w: w ϵ {0,1}* , Binary no. represented by w is exactly divisible by 5}
    [eg. (1010)2 =(10)10 is exactly divisible by 5, so it should be accepted]
    Use it to check whether “01111” and “1101” are exactly divisible by 5 or not.
    3. Construct NFA for following Languages:
    a. L = (ba ∪ baa)*
    b. L = {w: w ϵ {0,1}* , w ends with “1100”}
    c. L = b*a(b ∪ a)*baa
    d. L = {w: w ϵ {0,1}* , Length of w is at-least 5}
    e. L = {w: w ϵ {a,b}* , w contains “baa” or starts with “aba”}
    4. Convert above NFAs (in question no. 3) to their equivalent DFAs.
    5. Convert Following NFAs to DFAs
    a. b.
    a e 1 0
    q0 q1 q4 q1 q2 q3
    e
    a q0 0, 1
    e, b e a
    e
    1
    q2 b q3 q4 0 q5 q6
    a 0, 1

    6. Use Pumping Lemma to show whether following Languages are Regular or not.
    a. L = {w: w ϵ {a,b}* , w contains equal nuber of ‘a’ and ‘b’}
    b. L = { anbncn : n ≥ 0}
    c. L = { an! : n ≥ 0}
    d. L = { anbm : m > n}
    e. L = {w: w ϵ {a,b}* , Number of ‘a’ in w is greater than number of ‘b’}
    f. L = {wwR : w ϵ {0,1}*}
    g. L = { anb2n : n ≥ 1}
    Chapter 2 (Theory of Computation)

    7. Minimize Following DFAs


    a. DFA represented by following Transition Table
    ∑
    a b
    Q
    →q0 q3 q1
    q1 q3 q2
    q2 q4 q1
    *q3 q4 q3
    *q4 q4 q4
    q5 q4 q2
    Here, ‘→’ represents starting state and ‘ * ’ represents Final States.
    b. DFA represented by following State Transition Diagram

    0 1

    q0 0 q1 1 q2 0
    q3
    1 0 1 1
    0

    1 1 0
    q4 q5 q6 q7
    1
    0

    c. DFA represented by following State Transition Diagram


    a,b a
    b q2 b q4 a
    q0 2 q6
    a b a b
    b b
    b a b
    q1 q3 q5 q7
    a
    8. Consider regular grammar G = (V, ∑, R, S) where
    V = {S, A, B, a, b}, ∑ = {a, b}
    R = { S → abA | B | baB | e , A → bS | A , B → aS }
    Construct the finite automata M such that L(M) = L(G). [IOE, 2070 Chaitra]
    9. Show that the class of Regular Language is closed under Union and Concatenation
    operations.
    10. Show that for any regular expression R, there is a NFA that accepts the same regular
    language represented by R.
    ***

    You might also like