On Regular Expressions

In assignments for this class, we'll be trying to use regular expression syntax that matches POSIX regexes whenever possible. This means the following notations.

• x|y means union of languages of x and y
• x* means the Kleene closure of the language of x
• x+ is shorthand for xx*. Intuitively, it means "one or more x". It it sometimes referred to as the Kleene plus.

Dear Class,

Office hour changes:

Aashish Jindia (ajindia@andrew)
Office Hours: Sunday, 6-8pm, Wean 5316

Andrew Smith (adsmith@andrew)
Office Hours: Monday 5:45-7:45pm, Room GHC 7101
(If room is occupied at first, meet in the Gates 7th floor Atrium) 

We may add another office hour on Fridays, check the FLAC homepage.

Project: 
As soon as you choose your topic, you can post your title by clicking "Post title" on the FLAC Project Info page. You can see who has posted by clicking "View list."

Homework: 
Please do each problem on a separate sheet. Make sure your name is on each page. Make sure you include your References. You won't get any credit for your HW without that.  

See you in class!
-lenore 

Clarification on Homework 1 Question 4

It has come to my attention that a number of you have come up against a similar problem in Question 4. While trying to describe an algorithm to construct a DFA for L1/L2 from a DFA for L1, you need to make some part of this DFA depend on the existence of some string. However, there doesn't seem to be any obvious way to determine if such a string exists.

If you're doing this problem in the most intuitive way, you don't see a way to determine if the string exists because there actually isn't any algorithm to always tell you. This relates to the idea of computability, which you'll see a lot of later in the course.

The good news for you is that you don't have to give an algorithm for this! The key idea here is that you are trying to argue that there is a DFA recognizing the language L1/L2. You don't need to show how to construct DFA, as long as you can prove that it exists. This is the difference between a constructive proof and an existence proof (see http://en.wikipedia.org/wiki/Constructive_proof).

So, you can say things like "this hypothetical DFA satisfies delta(q,x)=q_i if there is a string with this property, and delta(q,x)=q_j if there is no such string." If I were a reader trying to adapt this proof to construct an actual DFA, I'd be pretty mad at you -- how should I know if there is such a string? But in this case I'm not trying to construct a DFA, as long as I know one is out there. While the sentence "there is a string with property X" might not be computable, it is a logical statement (in second-order logic, as it happens) and has a value of true or false. Therefore it is valid to describe a DFA in terms of the truth or falsehood of this statement.

If you'd been asked to explicitly give a DFA, as you are in problems 1 or 2, an argument like this would not answer the question. But since you only need to prove that a DFA exists, you're perfectly fine saying "this state is initial if and only if Y" without describing how to verify the property Y, as long as Y is a valid logical statement.

If anyone is still confused on this point, come to my office hours on Monday and I'll be happy to explain further.

Notes about HW1

Hey guys, a few notes about HW1:

1) Your DFAs don't necessarily have to be the absolute smallest possible, but they should be reasonable. If your DFA has extra states that you could easily do without, we may take off points. Mostly, they should logically make sense. We don't expect crazy tricks.

2) To prove that a DFA recognizes a language, you need to argue two points: (a) every string in the language is accepted by the DFA, and (b) only the strings in the language are accepted by the DFA. It doesn't have to be a very rigorous proof, but you should make logical and clear arguments as to why these points are true

3) If you draw a DFA, you don't need to give the tuple definition. 

    In Problem 3 on the homework, you need to describe a DFA that accepts Max(A) given a DFA for A.

    For questions like this one, you will have to provide the tuple definition of the DFA for Max(A) assuming the tuple definition for the DFA for A, since you cannot give an explicit DFA because A is abstract.

This would look something like: 

Assume the DFA for A is of the form M = {Q, \Sigma, \delta, q_0, F}.

We define the DFA for Max(A) as : M ' = {Q', \Sigma , \delta ', q_0 ', F' }, where

Q' = ....

\delta' = ....

q_0' = ....

F' = ....

You should also just describe in words how you are modifying the DFA for A and why this modification works.

Hello, I'm Andy. I'm a junior in SCS and I will be the other TA for FLAC.

Hi everyone, I'm Aashish, a senior in SCS. I will be one the TAs for this class.