Compiler Construction/Spring 2022 Homework 2
1 String Matching
Question 1.1 (3 points). Considering the alphabet Σ = {0, 1}, give a basic regular expression for each
of the following languages:
Copyright By PowCoder代写 加微信 powcoder
1. All strings that start and end with the same symbol. 2. All strings that have an odd length.
3. All strings that do not contain the substring 10.
Question 1.2 (3 points). Consider the following regular expression: a((b|c)d+)*
Give an NFA that accepts the same language. Question 1.3 (6 points). Consider the following NFA:
ε XX1 x GG2
Describe informally the strings accepted by this NFA. Give a DFA that accepts the same language. Question 1.4 (6 points). Consider the following DFA:
c a,c start GG b GG
tt 2 a,b,c
Give a regular expression that accepts the same language.
Adapted from CSCI-GA.2130-001 assignments by and .
Page 1 of 2
Question 2.1 (3 points). Investigate the documentation (https://jflex.de/manual.html) and
source code of JFlex (https://github.com/jflex-de/jflex) to answer the following questions: 1. What algorithm does JFlex use to construct the DFA?
2. What algorithm does JFlex use to minimize the DFA?
3. Using what pattern may greatly increase the number of DFA states?
Question 2.2 (4 points). Study the JFlex manual (https://jflex.de/manual.html) and examples (https://github.com/jflex-de/jflex/tree/master/jflex/examples/) to familiarize yourself with JFlex, then write a JFlex program that transforms its input as follows:
• Directive setname
• Directive name is replaced with the previously set name. Thus, your program should transform:
setname I met name. name lives nearby.
setname I met name. name lives nearby too.
into (what to leave in place of setname
Yesterday I met Alice. Alice lives nearby.
Today I met Bob. Bob lives nearby too.
Make sure to actually perform this exercise on a computer. Setting up a development environment where you can experiment with JFlex is part of the challenge and will serve you well in the project.
Question 2.3 (5 points). Write a JFlex program that transforms its input as follows:
• Directives beginnames and endnames delimit a section containing an arbitrary number of names.
• Directive names is replaced with the names previously listed between beginnames and endnames. Thus, your program should transform:
beginnames
Yesterday I met names. names live nearby.
into (the exact way of inserting and’s or other separators is not important):
Yesterday I met Alice and Bob and Chara. Alice and Bob and Chara live nearby.
Adapted from CSCI-GA.2130-001 assignments by and . Page 2 of 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com