Scribd Logo
Upload

Welcome to Scribd!

  • 95 views

    Automata Theory Exams

    Uploaded by

    Fırat Can
    1. The document contains an exam practice problem with 8 multiple choice questions about concepts related to finite state machines and regular languages. 2. The first problem asks about the result of executing a query Q against a database D. The remaining problems involve regular expressions, finite state machines, regular and non-regular languages, closure properties of regular languages, and statements about their properties. 3. The problems cover topics like regular expressions, deterministic and nondeterministic finite state machines, closure properties of regular languages, and statements about their properties like whether certain operations preserve regularity.

    Copyright:

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

    Automata Theory Exams

    Uploaded by

    Fırat Can
    95 views2 pages
    1. The document contains an exam practice problem with 8 multiple choice questions about concepts related to finite state machines and regular languages. 2. The first problem asks about the result of executing a query Q against a database D. The remaining problems involve regular expressions, finite state machines, regular and non-regular languages, closure properties of regular languages, and statements about their properties. 3. The problems cover topics like regular expressions, deterministic and nondeterministic finite state machines, closure properties of regular languages, and statements about their properties like whether certain operations preserve regularity.

    Original Description:

    automata theory exams

    Original Title

    automata theory exams

    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 contains an exam practice problem with 8 multiple choice questions about concepts related to finite state machines and regular languages. 2. The first problem asks about the result of executing a query Q against a database D. The remaining problems involve regular expressions, finite state machines, regular and non-regular languages, closure properties of regular languages, and statements about their properties. 3. The problems cover topics like regular expressions, deterministic and nondeterministic finite state machines, closure properties of regular languages, and statements about their properties like whether certain operations preserve regularity.

    Copyright:

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

    Automata Theory Exams

    Uploaded by

    Fırat Can
    1. The document contains an exam practice problem with 8 multiple choice questions about concepts related to finite state machines and regular languages. 2. The first problem asks about the result of executing a query Q against a database D. The remaining problems involve regular expressions, finite state machines, regular and non-regular languages, closure properties of regular languages, and statements about their properties. 3. The problems cover topics like regular expressions, deterministic and nondeterministic finite state machines, closure properties of regular languages, and statements about their properties like whether certain operations preserve regularity.

    Copyright:

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

    Name:

    1 10
    2 a 5
    b 10 CS 341
    3 10 First Midterm Exam
    4 a 15 Practice
    b 15
    c 15
    d 15 1. Use extra paper to determine your solutions then neatly transcribe
    5 a 5 them (including intermediate steps) onto these sheets.
    b 15 2. It’s possible that you won’t be able to finish. Read through the
    c 15 whole exam once and start working on the problems you’re sure you
    6 15 know how to do. Come back to the harder ones as you have time.
    7 15
    8 a 5
    b 5
    c 5
    Total 175

    (1) Consider the following problem: Given a database D and a query Q, what result is returned
    when Q is executed against D?

    (2) Let L = {w ∈ {a, b}* : w does not end in ab}


    (a) Show a regular expression that generates L.

    (b) Show an FSM that accepts L.

    (3) Show a (possibly nondeterministic) FSM that accepts {w ∈ {a, b}* : w contains at least one
    instance of aaba, bbb or ababa}.

    (4) For each of the following languages L, state whether it is regular or not and prove your answer.
    (a) {x#y: x, y ∈ {0, 1}*, when viewed as binary numbers, x+y = 3y}. Example: 1000#100 ∈ L.

    (b) Let Σ = {a, b}. L = {w ∈ Σ*: (w contains the substring ab) → (w contains the substring ba)}

    (c) {w = xyzy : x, y, z ∈ {0, 1}+}.

    (d){w = st : s ∈ {a, b}* and t ∈ {b, c}* and #b(s) = 2⋅#a(s) and #c(t) = 3⋅#b(t)}.
    (5) Recall that maxstring(L) = {w: w ∈ L and ∀z∈Σ* (z ≠ ε → wz ∉ L)}.
    (a) What is maxstring(L1L2), where L1 = {w ∈ {a, b}* : contains exactly one a} and L2 = {a}?

    (b) Prove that the regular languages are closed under maxstring.

    (c) If maxstring(L) is regular, must L also be regular? Prove your answer.

    (6) Consider the following NDFSM M. Use ndfsmtodfsm to construct an equivalent DFSM. Begin
    by showing the value of eps(q) for each state q:

    1 ε,a 2 b 3 b 4 a 5

    ε ε
    a,b

    (7) Define a decision procedure to answer the following question. You may use as subroutines all
    the procedures that we have discussed in class. Let Σ = {a, b} and let α and β be regular
    expressions. Is the following sentence true:

    (L(β) = a*) ∨ (∀w (w ∈ {a, b}* ∧ |w| even) → w ∈ L(α))

    (8) Prove or disprove each of the following statements:


    (a) It is possible that the intersection of an infinite number of regular languages is not regular.
    (b) Every subset of a regular language is regular.
    (c) Let L4 = L1L2L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regular.

    You might also like