Finite State Automata and Languages

We can recursively define ∑* as the smallest set such that

1) ε is in ∑*, and 

2) for all c in ∑, for all y' in ∑*, y'c is in ∑*.

With this definition in mind, we can prove properties about strings through structural induction - I will probably give more examples in the future. Thm 7.4 seems to be a good start, because it reflects the definition of ∑* above, namely that if we are trying to prove a property (for all strings y).P(y) using structural induction, we just assign y = y'c above, and assume P(y'), and proceed to show that (for all c in ∑).P(y).

DFSA Stingy Vending Machine:

- The Table of ∂ represents exactly the (deterministic) mappings of ∂: Q x ∑ --> Q (regardless of beginning state), so it is clear to me that the table is ∂ itself in the quintuple that describes automations.

In terms of the extended transition function ∂*, I read def'n 7.11 on pg.201 of the textbook to see exactly how it is defined by structural induction. In terms of the lecture, I can now see the significance of setting s = s'a when ∂*(q, s), so that we can determine when s' is in ∑* and a is in ∑, and so we can show that ∂*(q, s) = ∂(∂*(q, s'), a) in this case.

----------------------------------------------------------------------------------------------------------------------------------

Term Test 2:
- Got what I expected, I know what/how to do the questions now (as shown by previous blog posts).

Program correctness:

- Withholding practice until exam time.