Scribd Logo
Upload

Welcome to Scribd!

  • 53 views

    Exercises Unit3 Part2 OCW

    Uploaded by

    compiler&automata
    1. The document describes exercises on finite automata based on formal languages and automata theory. It includes exercises to design DFAs for specific languages over alphabets, determine languages recognized by given automata, calculate state complexity, verify automata equivalence, and obtain minimal DFAs.

    Copyright:

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

    Exercises Unit3 Part2 OCW

    Uploaded by

    compiler&automata
    53 views5 pages
    1. The document describes exercises on finite automata based on formal languages and automata theory. It includes exercises to design DFAs for specific languages over alphabets, determine languages recognized by given automata, calculate state complexity, verify automata equivalence, and obtain minimal DFAs.

    Original Description:

    automata

    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 describes exercises on finite automata based on formal languages and automata theory. It includes exercises to design DFAs for specific languages over alphabets, determine languages recognized by given automata, calculate state complexity, verify automata equivalence, and obtain minimal DFAs.

    Copyright:

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

    Exercises Unit3 Part2 OCW

    Uploaded by

    compiler&automata
    1. The document describes exercises on finite automata based on formal languages and automata theory. It includes exercises to design DFAs for specific languages over alphabets, determine languages recognized by given automata, calculate state complexity, verify automata equivalence, and obtain minimal DFAs.

    Copyright:

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

    Formal Languages and Automata Theory

    Formal Languages and Automata Theory


    Exercises Finite Automata
    Unit 3 – Part 2

    Authors:
    Araceli Sanchis de Miguel
    Agapito Ledezma Espino
    Jose A. Iglesias Martínez
    Beatriz García Jiménez
    Juan Manuel Alonso Weber

    * Several exercises are based on the ones proposed in the following books:
     Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón.
    Teoría de autómatas y lenguajes formales. McGraw-Hill (2007).
     Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga. Teoría de lenguajes,
    gramáticas y autómatas. Publicaciones R.A.E.C. (1997).
     Pedro Isasi, Paloma Martínez y Daniel Borrajo. Lenguajes, Gramáticas y Autómatas.
    Un enfoque práctico. Addison-Wesley (1997).
    Formal Languages and Automata Theory

    1. Indicate the graph of a DFA which recognizes each one of the following languages. The
    alphabet is {0, 1}.
    a) The language {0}
    b) The language 0m1n0p ( m ≥ 0,n ≥ 0, p ≥1 )

    2. Indicate which is the language recognized by the FA2.

    AF 2 0 ,1
    0
    S C

    1 1
    0

    1
    A B

    3. [Exam] We have a door with only one lock. To open it, it is necessary to use three
    different keys (called a, b, and c), in a predefined order, which is following described:

     Key a, then key b, then key c, or


     Key b, then key a, then key c.

    If this order is not followed, then the lock is blocked (for instance, if the key a is used and
    following it is introduced again).

    Once the door is open, the introduction of keys in the lock (in every possible order) does
    not affect the closing device (i.e. the door remains open).

    Consider that the names of the different keys are symbols of an alphabet, over which a
    language L whose words are the valid sequences for the opening of the door is defined.
    For instance, abcbc is a word included in the language.

    It is required:

    a) Design a finite automata FA which accepts L.


    b) (After Unit 5) Grammar (clean and well-formed) which generates words in L.
    Formal Languages and Automata Theory

    4. Calculate the Q/E of the following automata:

    1
    0
    q2 1
    q1

    0
    1
    0 1 q2
    q0 q1

    0 0,1

    5. Given the following DFA, obtain the minimal equivalent DFA.


    Formal Languages and Automata Theory
    6. Verify if the following two DFA are equivalent (by obtaining the minimal DFA for each
    one of them).

    1
    AF 3 1

    1 1 0
    q1 q3 q5 q7

    1 0
    0 0
    1 1 1

    q2 q4
    0 q6 q8
    0
    0 0

    7. Obtain the minimal DFA for the following DFA.

    DFA_1=({a,b,c},{Q0,Q1,Q2,Q3,Q4},f,Q0,Q3)

    f(Q0, a) = Q1 ; f(Q0, b) = Q2 ; f(Q0, c) = Q3


    f(Q1, a) = Q2 ; f(Q1, b) = Q3 ; f(Q1, c) = Q1
    f(Q2, a) = Q3 ; f(Q2, b) = Q1 ; f(Q2, c) = Q3
    f(Q3, a) = Q4 ; f(Q3, b) = Q4 ; f(Q3, c) = Q4
    f(Q4, a) = Q4 ; f(Q4, b) = Q4 ; f(Q4, c) = Q4

    DFA_2; =({a,b,c}, {Q0,Q1,Q3,Q4,Q5,Q6,Q8},f,Q0,{Q3,Q4,Q6,Q8})

    f(Q0, a) = Q4 ; f(Q0, b) = Q5 ; f(Q0, c) = Q1


    f(Q1, a) = Q5 ; f(Q1, b) = Q5 ; f(Q1, c) = Q3
    f(Q3, a) = Q5 ; f(Q3, b) = Q5 ; f(Q3, c) = Q5
    f(Q4, a) = Q4 ; f(Q4, b) = Q8 ; f(Q4, c) = Q1
    f(Q5, a) = Q5 ; f(Q5, b) = Q5 ; f(Q5, c) = Q5
    f(Q6, a) = Q5 ; f(Q6, b) = Q8 ; f(Q6, c) = Q5
    f(Q8, a) = Q5 ; f(Q8, b) = Q6 ; f(Q8, c) = Q5
    Formal Languages and Automata Theory

    DFA_3=({a,b,c},{Q0,Q1,Q2,Q3,Q4,Q6,Q7,Q8,Q9},f,Q0,{Q7,Q8})

    f(Q0, a) = Q1 ; f(Q0, b) = Q6 ; f(Q0, c) = Q6


    f(Q1, a) = Q7 ; f(Q1, b) = Q2 ; f(Q1, c) = Q6
    f(Q7, a) = Q7 ; f(Q7, b) = Q2 ; f(Q7, c) = Q6
    f(Q2, a) = Q6 ; f(Q2, b) = Q8 ; f(Q2, c) = Q6
    f(Q8, a) = Q6 ; f(Q8, b) = Q8 ; f(Q8, c) = Q4
    f(Q4, a) = Q6 ; f(Q4, b) = Q9 ; f(Q4, c) = Q3
    f(Q9, a) = Q6 ; f(Q9, b) = Q8 ; f(Q9, c) = Q4
    f(Q3, a) = Q6 ; f(Q3, b) = Q9 ; f(Q3, c) = Q4
    f(Q6, a) = Q6 ; f(Q6, b) = Q6 ; f(Q6, c) = Q6

    DFA_4=({c,f,d},{Q0,Q5,Q8,Q9,Q10,Q11,Q12},f,Q0,Q10)

    f(Q0, c) = Q9 ; f(Q0, f) = Q10 ; f(Q0, d) = Q8


    f(Q9, c) = Q9 ; f(Q9, f) = Q11 ; f(Q9, d) = Q12
    f(Q10, c) = Q0 ; f(Q10, f) = Q8 ; f(Q10, d) = Q8
    f(Q11, c) = Q11 ; f(Q11, f) = Q11 ; f(Q11, d) = Q8
    f(Q12, c) = Q12 ; f(Q12, f) = Q5 ; f(Q12, d) = Q5
    f(Q5, c) = Q5 ; f(Q5, f) = Q5 ; f(Q5, d) = Q8
    f(Q8, c) = Q8 ; f(Q8, f) = Q8 ; f(Q8, d) = Q8

    You might also like