CS3331 – Assignment 1
due Oct. 8, 2024
2-day no-penalty extension until: Oct. 10, 11:59pm
1. (40pt) For each of the following languages, prove whether it is regular or not. If it is, then:
- construct a NDFSM for it
- convert the NDFSM into a DFSM (include trap/dead states)
- minimize the DFSM
- convert one of the machines into a regular expression; give a simple regular expression; you may have to construct it directly if the machines give horrible expressions
Show your work. If you can give directly a DFSM, then you don’t have to provide a NDFSM. If you provide directly the minimal DFSM, you still need to argue why it is minimal.
(a) L = {w ∈ {a, b}* | w = xxzyy, for some x,y, z ∈ {a, b}* }.
(b) L = {w ∈ {a, b}* | ww Rw = wR ww R }.
(c) L = {w ∈ {a, b}* | w has ababa as a substring}.
(d) L = {w ∈ {a, b}* | w has aa and bb as substrings, but not aba} (do not give a reg. exp. here).
(e) L = {w ∈ {a, b}* | w starts and ends with the same non-empty string diferent from w}.
(f) L = {w ∈ {a, b}* | #a (w) 三 2#b (w) (mod 3)} (do not give a reg. exp. here).
(g) L = {w ∈ {a, b}* | (#a (w) - #b (w))|#a (w)}.
(h) L = {w ∈ {a, b}* | if #a (w) is prime, then #a (w)|(#b (w)#a (w) - #b (w))}.
2. (20pt) This question concerns the multi-pattern matching and searching (see slides 43-45 of Regular Expressions chapter) problems; assume the English alphabet Σ = {a, b, . . . , z}.
(a) (10pt) Construct the minimal DFAs to solve the multi-pattern matching and searching problem for the patterns p1 = for, p2 = or, p3 = xor (one DFA for matching and one for searching).
(b) (5pt) Write a (pretty) regular expression for each language, L, accepted by the DFAs at (a).
(c) (5pt) For each L above, how many equivalence classes does ≈L have? Indicate one string for each class.
Show your work. You can use Thomson’s construction, or directly build a correct NDFSM or DFA, or even the minimal DFA. Either way, you need to argue why your construction is correct.
3. (20pt) Consider a programming language where identifiers, Id, are sequences of (English) letters, (decimal) digits, and underscores that start with a letter. The language contains also of a set of keywords, Key, which are certain non-empty strings consisting of letters only; keywords are reserved and cannot be used as identifiers.
(a) (10pt) If the keywords are Key = {con, cost, const}, then construct the minimal DFA for the language (Id - Key) ∪ Key{#}.
(b) (10pt) Assuming that εx∈Key |x| = 10, give an example of Key which produces the minimal
DFA for the set (Id - Key) ∪ Key{#} with the smallest number of states. Show the DFA.
4. (20pt) Prove that the following problems are decidable:
(a) (10pt) Given a regular language L over {a; b}, is it true that L contains infinitely many strings that have at least one a but finitely many strings that have at most one b?
(b) (10pt) Given two regular languages, L1 and L2 , is it true that every string in L1 is a prefix of a concatenation of strings from L2 ?
You are allowed to use any of the following:
– closure properties: union, concatenation, Kleene star, complement, intersection, diference
– conversion algorithms between DFSM, NDFSM, regular expressions, and regular grammars (see the last slide of Ch.7: Conversions)
– decision algorithms: membership, emptiness, finiteness, totality, equivalence, minimality.
Explain clearly which of the above closure property and algorithm you have used at each step. Any other construction or algorithm should be described in the assignment.
Notes: !!! Submit your solution as a single pdf file; anything else receives 0pt. Solutions should be typed but high-quality hand-written solutions are acceptable.
JFLAP: You are allowed to use JFLAP to help you solve the assignment. You still need to explain clearly your solution. Also, make sure you understand what it does; JFLAP will not be available during exams!
LLMs: You are allowed to use LLMs (Large Language Models), such as ChatGPT, but, again, they will not be available during exams.
LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to all the other programs, it is free, and you can start using it in minutes; here is an introduction: https://tobi.oetiker.ch/lshort/lshort.pdf. It is also available online at https://www.overleaf.com/.