Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    CSI 409: DFA Design Problems Some Answers and Hints

    Uploaded by

    Faizan Raheem
    The document provides examples and solutions for DFA design problems over various languages: 1. It disproves that A ◦ (B ∩ C) = (A ◦ B) ∩ (A ◦ C) by providing a counter example. 2. It disproves that A ( B → A∗ ( B ∗ by providing the languages A = {a} and B = {ε, a} as a counter example. 3. It constructs DFAs for the languages: (a) strings with total symbol count as an even number, (b) strings starting with a but not containing aab, (c) the union of (ab)* and a

    Copyright:

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

    CSI 409: DFA Design Problems Some Answers and Hints

    Uploaded by

    Faizan Raheem
    29 views3 pages
    The document provides examples and solutions for DFA design problems over various languages: 1. It disproves that A ◦ (B ∩ C) = (A ◦ B) ∩ (A ◦ C) by providing a counter example. 2. It disproves that A ( B → A∗ ( B ∗ by providing the languages A = {a} and B = {ε, a} as a counter example. 3. It constructs DFAs for the languages: (a) strings with total symbol count as an even number, (b) strings starting with a but not containing aab, (c) the union of (ab)* and a

    Original Description:

    This is very helpful

    Original Title

    Project

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides examples and solutions for DFA design problems over various languages: 1. It disproves that A ◦ (B ∩ C) = (A ◦ B) ∩ (A ◦ C) by providing a counter example. 2. It disproves that A ( B → A∗ ( B ∗ by providing the languages A = {a} and B = {ε, a} as a counter example. 3. It constructs DFAs for the languages: (a) strings with total symbol count as an even number, (b) strings starting with a but not containing aab, (c) the union of (ab)* and a

    Copyright:

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

    CSI 409: DFA Design Problems Some Answers and Hints

    Uploaded by

    Faizan Raheem
    The document provides examples and solutions for DFA design problems over various languages: 1. It disproves that A ◦ (B ∩ C) = (A ◦ B) ∩ (A ◦ C) by providing a counter example. 2. It disproves that A ( B → A∗ ( B ∗ by providing the languages A = {a} and B = {ε, a} as a counter example. 3. It constructs DFAs for the languages: (a) strings with total symbol count as an even number, (b) strings starting with a but not containing aab, (c) the union of (ab)* and a

    Copyright:

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

    CSI 409: DFA design problems

    Some answers and hints

    1. Disprove the following: A ◦ (B ∩ C) = (A ◦ B) ∩ (A ◦ C) for all languages A, B, C.

    Take A = {, a}, B = {}, C = {a}.

    2. Disprove the following: for all languages A, B


    A ( B → A∗ ( B ∗

    Take A = {a} and B = {, a}.

    3. Construct deterministic finite automata (DFAs) recognizing the following languages over the
    alphabet {a, b}:

    (a) {ai bj | i ≥ 0, j ≥ 0, i + j is an even number}

    0 1

    b b
    b

    2 3
    b

    a a

    a,b
    (b) The set of all strings that begin with a but do not contain aab as a substring.

    a
    b a

    a a
    0 1 2

    b b

    a, b

    (c) (ab)∗ ∪ a

    a b a
    0 1 2 3

    b a b a

    a, b

    2
    (d) b(aa)∗

    b
    1 2 4

    a b b

    a, b

    4. Consider the language a∗ b ∪ b∗ over the alphabet {a, b}. Show that any DFA that accepts
    this language has to contain a dead state.

    No string that has ba as a prefix is in the language.

    You might also like