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

Welcome to Scribd!

  • 11 views

    FL 2020 21 Apr

    Uploaded by

    Nicolo' Molinari
    (1) The document provides instructions for a midterm exam on formal languages and compilers. It contains 5 problems testing knowledge of regular languages, finite automata, context free grammars, and grammar simplification techniques. (2) Students are expected to maintain academic integrity and show their work clearly. The exam is open book and scans of work must be uploaded after completion. (3) Problem 1 contains questions about properties of regular languages and uses the pumping lemma. Problem 2 involves constructing regular expressions, deterministic finite automata, and context free grammars. Problems 3-5 deal with converting between models of computation like NFAs, epsilon-NFAs, and simplifying context free grammars.

    Copyright:

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

    FL 2020 21 Apr

    Uploaded by

    Nicolo' Molinari
    11 views2 pages
    (1) The document provides instructions for a midterm exam on formal languages and compilers. It contains 5 problems testing knowledge of regular languages, finite automata, context free grammars, and grammar simplification techniques. (2) Students are expected to maintain academic integrity and show their work clearly. The exam is open book and scans of work must be uploaded after completion. (3) Problem 1 contains questions about properties of regular languages and uses the pumping lemma. Problem 2 involves constructing regular expressions, deterministic finite automata, and context free grammars. Problems 3-5 deal with converting between models of computation like NFAs, epsilon-NFAs, and simplifying context free grammars.

    Original Description:

    Original Title

    FL-2020-21-Apr

    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 provides instructions for a midterm exam on formal languages and compilers. It contains 5 problems testing knowledge of regular languages, finite automata, context free grammars, and grammar simplification techniques. (2) Students are expected to maintain academic integrity and show their work clearly. The exam is open book and scans of work must be uploaded after completion. (3) Problem 1 contains questions about properties of regular languages and uses the pumping lemma. Problem 2 involves constructing regular expressions, deterministic finite automata, and context free grammars. Problems 3-5 deal with converting between models of computation like NFAs, epsilon-NFAs, and simplifying context free grammars.

    Copyright:

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

    FL 2020 21 Apr

    Uploaded by

    Nicolo' Molinari
    (1) The document provides instructions for a midterm exam on formal languages and compilers. It contains 5 problems testing knowledge of regular languages, finite automata, context free grammars, and grammar simplification techniques. (2) Students are expected to maintain academic integrity and show their work clearly. The exam is open book and scans of work must be uploaded after completion. (3) Problem 1 contains questions about properties of regular languages and uses the pumping lemma. Problem 2 involves constructing regular expressions, deterministic finite automata, and context free grammars. Problems 3-5 deal with converting between models of computation like NFAs, epsilon-NFAs, and simplifying context free grammars.

    Copyright:

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

    Free University of Bozen-Bolzano – Faculty of Computer Science

    Bachelor in Computer Science


    Formal Languages and Compilers – A.Y. 2020/21
    MidTerm – 21/04/2020
    Alessandro Artale
    Time: 1h 40 minutes
    Student Code Ethics
    Students are expected to maintain the highest standards of academic integrity. Work
    that is not of the student’s own creation will receive no credit, and disciplinary ac-
    tions can follow. Remember that you cannot give or receive unauthorized aid on any
    assignment, quiz, or exam. A student cannot use the ideas of another and declare it
    as his or her own.
    This is an open book exam.
    Write in every sheet: Name, Surname, STUDENT-ID, email.
    When you finish, make a scan, name it with your STUDENT-ID, and Upload it in the
    folder MidTerm under this Team.
    Write clearly, in the sense of logic, language and legibility. The clarity of your
    explanations affects your grade.

    Problem 1 [11 points] Decide which of the following statements is TRUE and which is FALSE.
    Answering just TRUE or FALSE does not give marks, you MUST give a brief explanation of your
    answer to receive marks.

    (a) Every subset of a regular language is regular. [3 Pt.]


    (b) Let L1 , L2 be two regular languages over the same alphabet Σ, then the language L = {w ∈ Σ∗ |
    w∈/ L1 or w ∈ L2 } is regular. [2 Pt.]
    (c) The language L over the alphabet Σ = {(, )} defined as, L = {(n )n | n ≥ 1}, is regular (use the
    Pumping Lemma). [3 Pt.]
    (d) In Unary Notation numbers are represented using only the symbol 1, thus 5 would be represented as
    11111 in unary notation. Say whether or not the following language is a regular language: [3 Pt.]
    L = {w | w is the unary notation for a multiple of 4}

    Problem 2 [10 points]

    (a) Construct the Regular Expression that generates the language over the alphabet Σ = {x, y, z}
    constituted by all strings in which each x is immediately preceded or immediately followed (or both)
    by y. E.g., zzyxxyyzzyxyzxy ∈ L(A), while zzyxxz 6∈ L(A), zzyxxxy 6∈ L(A). [3 Pt.]
    (b) Construct the Deterministic Finite Automaton (DFA) over the alphabet Σ = {a, b, c} which
    accepts the language of all words that begin with a sequence of one or more a’s and end with the
    letter b. For example, the DFA must accept abacb and aaacbbab, but not cab. [3 Pt.]
    (c) Construct a Context Free Grammar for the language L over the alphabet {a, b, c, d} such that
    L = {an bm cm d2n | n ≥ 0 and m > 0}. E.g., bc ∈ L, bbcc ∈ L, aabbccdddd ∈ L, while abc 6∈ L,
    add ∈
    / L, abcd ∈
    / L. [4 Pt.]

    Problem 3 [4 points] From NFA to DFA. Consider the following NFA AN over {a, b}:
    a a
    (a) Construct a DFA AD such that L(AD ) =
    b b L(AN ). Show only the transition table. The
    b q3
    (ii)
    a
    b algorithm you have followed to construct AD
    q0 q1 q2
    b should become evident in your construction.
    (b) Show all possible sequences of states of the
    Exercise 3.15. (o65)
    NFA, AN , that are traversed when the input is
    Convert the following NFA to a DFA.
    the string abaa, and say whether the string is
    a,b
    accepted.
    a,b

    a a a
    start 0 1 2 3
    Problem 4 [4 points] From -NFA to NFA. Consider the following ε-NFA A over {0, 1}:
    (a) Show the -closure of each state.
    1,ε 0 1
    ε 0,1 (b) Construct an NFA, AN , such that L(AN ) = L(A ). Show
    A B
    C only the transition table. The algorithm you have followed
    0 0, ε
    to construct AN should become evident in your construc-
    0,ε tion.
    D
    1

    
    Problem 5 [4 points] Given the following context free grammar G = {S, A, B, C}, {a, b}, P, S , where
    P consists of the following productions:

    S −→ B | BaBb | AbB B −→ Bb | AC | 
    A −→ Ab | AC C −→ AC | CB | Ba

    Apply the sequence of steps that are necessary to simplify the context free grammar and convert it into
    a Clean-up Form.

    Note 1: The sequence of steps must be in the right order!


    Note 2: The algorithms adopted in each step of the semplification procedure must be Clearly Pre-
    sented showing the various intermediate steps.

    You might also like