Another sample midterm question

I already mentioned this in lecture, and you may remember it ... but it's worth thinking through.  This question was required for students in CIS 561 and optional extra credit for students in CIS 461.

L is the set of all sequences of one or more decimal digits in which each digit appears at most once.  For example, "0152" is in L, and "520" is in L, but "9525" is not in L  (because 5 is repeated).

Is L a regular language?  If it is not regular, why not? If L is regular, how many states are in the smallest DFA that recognizes L?

The ID (identifier) token and what it represents

I was asked whether the scanner needs to recognize bad identifiers like foo.bar.baz .  The short answer is "no, that's a job for the parser", but the question indicates a need to be a little clearer about exactly what the identifier (ID) token represents.

foo.bar.baz is 5 tokens:  ID foo, DOT, ID bar, DOT, ID baz.  A scanner should in general not try to match anything with internal structure, like foo.bar(); it is returning the atoms of a program, to be assembled into molecules by the parser.    (I know the STRINGLIT token may seem like an exception, but from the parser's point of view it has no internal structure, even if the scanner has to do some work to interpret things like \n and \" inside the quoted string literal.)

Two more NFA => DFA problems for the board

1.  From the winter 2005 midterm, a language for binary or trinary literals.  A binary literal is
(0|1)+b2
and a trinary literal is
(0|1|2)b3
So for example 01110101b2 is a binary literal, 0110101b3 is a trinary literal and so is 01002201b3, but 010020101b2 is neither a binary literal nor a trinary literal.   Given an NFA for this, we'll construct the DFA.

2.  From the Spring 2006 midterm, a simplified quoted string problem.  A quoted string (string literal) starts with a quotation mark and ends with a quotation mark.  Within the string, we can have alphabetic characters.  To put a quotation mark within a quoted string, we type two quotation marks together, like this:
"this is a ""string with a quoted substring"" up to here"
If we let 'a' stand for alphabetic characters and Q stand for a quotation mark, the regular expression might be something like
Q(a|(QQ))*Q
We'll use the subset construction to derive a DFA from the NFA.

Regexp => NFA => DFA problem for tomorrow's class

The main things I want to do in class Friday are:

• work a few examples of translating regular expressions to non-deterministic finite-state acceptors
• discuss a few practical complications that aren't apparent in the theory, like how the "maximum munch" rule and matching a lot of different patterns (with different actions) go together
• discuss the limitations of lexical analysis (the pumping lemma, for those of you who took automata theory)

Here's a small example we can do on the board tomorrow, for the first two items above.  Imagine your language has integer constants and floating point constants.  Integer constants are a sequence of one or more integer digits.  It might be specified as
[0-9]+
or equivalently as
[0-9][0-9]+
Floating point constants consist of zero or more digits, followed by a decimal point, followed by one or more digits.  (So .00 is a floating point constant, but 0. is not, and neither is . )  This might be specified as
[0-9]*[.][0-9][0-9]*

We could carefully follow Thompson's construction to get the NFA for each of these and then combine them, but it's easier and less messy to just eyeball the pattern for integer constant and the pattern for floating point constant and create an automaton for each of them, then use Thompson's construction just to tie them together as
    ( integer constant ) |  (floating point constant )
and then we can go through the subset construction to get a single deterministic finite-state acceptor that is looking for both of them and succeeds if it matches either one.  You might want to try that in advance (but you don't have to).  If you do, consider what should happen with the following input:
998
99.foo
.998