Full exam for Formal Languages and Compilers in the Computer Engineering degree programme at Politecnico di Milano. The document covers: FORMAL LANGUAGES AND COMPILERS prof.s Luca Breveglieri and Angelo Morzenti Exam of Thu 18 JANUARY 2018 - Part Theory WITH SOLUTIONS - FOR TEACHING PURPOSES HERE THE SOLUTIONS ARE WIDEL Y COMMENTED LAST + FIRST NAME: (capital letters please) MATRICOLA: SIGNATURE: (or PERSON CODE)
Full exam for Formal Languages and Compilers in the Computer Engineering degree programme at Politecnico di Milano. The document covers: FORMAL LANGUAGES AND COMPILERS prof.s Luca Breveglieri and Angelo Morzenti Exam of Thu 18 JANUARY 2018 - Part Theory WITH SOLUTIONS - FOR TEACHING PURPOSES HERE THE SOLUTIONS ARE WIDEL Y COMMENTED LAST + FIRST NAME: (capital letters please) MATRICOLA: SIGNATURE: (or PERSON CODE)
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
FORMAL LANGUAGES AND COMPILERS prof.s Luca Breveglieri and Angelo Morzenti Exam of Thu 18 JANUARY 2018 - Part Theory WITH SOLUTIONS - FOR TEACHING PURPOSES HERE THE SOLUTIONS ARE WIDEL Y COMMENTED LAST + FIRST NAME: (capital letters please) MATRICOLA: SIGNATURE: (or PERSON CODE) INSTRUCTIONS - READ CAREFULLY: • The exam is in written form and consists of two parts: 1. Theory (80%): Syntax and Semantics of Languages – regular expressions and finite automata – free grammars and pushdown automata – syntax analysis and parsing methodologies – language translation and semantic analysis 2. Lab (20%): Compiler Design by Flex and Bison • To pass the exam, the candidate must succeed in both parts (th eory and lab), in one call or more calls separately, but within one year (12 months ) between the two parts. • To pass part theory, the candidate must answer the mandatory (not optional) ques- tions; notice that the full grade is achieved by answering th e optional questions. • The exam is open book: textbooks and personal notes are permi tted. • Please write in the free space left and if necessary continue on the back side of the sheet; do not attach new sheets and do not replace the existin g ones. • Time: part lab 60m - part theory 2h.15m 1 Regular Expressions and Finite Automata 20% 1. Consider the regular expression R1 below, over the two-letter alphabet { a, b }: R1 = ( a | ε )+ ( b a | b a b )∗ Consider also the non-deterministic automaton A2 below, over the same two-letter alphabet{ a, b }, with a spontaneous transition, and with final nodes 1 and 3: 1 2 3 4A2 → → → a b a b b ε Answer the following questions (use the spaces / tables on th e next pages): (a) Determine whether expression R1 is ambiguous, and explain your answer. (b) By first using the Berry-Sethi method and then…
First page of the document.
