Recursive Definitions

ch 3, 6, 7, 9, 15,16,19 

Finite Automata

ch 5 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19

When inputting data such as dates (7/3/99, 7/3/1999), SSN's (123-456-7898) phone numbers (1-(800)-555-1234) or IP address (149.543.8.8)  etc., you frequently want to define an input mask or a template of allowable symbols. Define the words in the language (patterns) of allowable dates, SSN's and phone numbers using regular expressions. { make sure to define your alphabet to include . ,  - ,  ( , ) }.Make sure that you can handle dates such as 9/7/99, 3/07/99 and 3/7/1999 and phone numbers without area codes (if you want to allow them). Create a FA (ch 5) and a transition diagram (ch 6) to test the validity of an input string and also write out the production rules of the grammar. for each. How would you write a program to test for validity. See notes3 for some thoughts.

In some languages such as Unix and JavaScript, regular expressions can be defined. How can this be used to quickly test for validity? Look up regular expressions in UNIX and JavaScript.)

ANOTHER EXAMPLE: Look at %d the prinf function in C such as printf("the maximum is: %d",MAX(x,y));.This is another example of the use of a mask. 

A more general problem: How can regular languages / FA be used to do pattern recognition.

• We will begin by showing how we can go from words in a language to regular expressions. 

• Next, we will show how to express words as Finite Automata (FA)  and show how to covert a  FA diagram into a regular expression (part of this will come part of the Kleene Theorem proof  from ch 7 pp. 93-108.)

Kleene Theorem

Make sure that you can follow a TG. 

• Next, we will look at transition diagrams, again looking at how they relate to regular expressions and to FA.

• Lastly, we will prove the second part of Kleene's Theorem, by converting regular expressions into FA. (pp. 108-135.

• We will end the two week discussion by showing that for every Non-deterministic Finite Automata (NFA), there is some FA that accepts exactly the same language (Theorem 7).

Regular languages

We will also go over the construction of a DFA from a NFA.

We will then show that they are equivalent. Lastly, we will discuss their use in such applications as sequential circuits (pp. 161-164), switching theory and operating systems. The Moore/Mealy machines are basically FA machines except that when we travel an edge we generate an output as well as going to a new state. For example, moving from a non-print state to a print state output printing. When the printing is done, the computer returns to the non-print state. There is a nice summary chart on p. 164.

Next, we will discuss regular languages (ch 9). This is a short chapter and somewhat of a review of what we have learned in terms of constructive proofs. In addition to the union and intersection we saw in ch. 7, ch 9 discusses complements and goes into intersection for another view.

The last point I want to cover is how to write out production rules for FA. (I may end up doing this while discussing the topics above since this is really just another way to show the same thing.) This is covered in ch 13, Grammatical Format, under the subtopic Regular Languages pp. 259-265. This method will give us a compact way to write out the steps of a FA and give us a chance to look at the grammar for FA's. What this amounts to is just writing going from state A to state B via a transition as A-->aB and then writing out all the transitions out in the same way. If you have a word/string and apply the production rules and end up in a final (terminal) state, the word/string is accepted. for an FA, you can write out its production rules; given production rules of a regular language, you can write out the FA.  

Decidability

23 

Grammatical Format

CFC=PDA

Mid -Term

. Open book test on ch 1-15

Decidability 

Post Machines

Variation on the TM

Chomsky Hierarchy

4/26

FINAL: W: MAY 3  project 3. will be due at the end of the semester.