Here is a typeset example hot off the laptop.
Here is some correspondence about this:
From: dhy3@cornell.edu Subject: CS 481: HW 1 what's the general paradigm for formally proving that a given machine accepts a given language?
From: aww6@cornell.edu To: Dennis Han YehSubject: Re: CS 481: HW 1 The general idea is to show two things: Suppose you are trying to prove that machine M accepts language L. 1. Show that any string in L leads to a final state in M. this implies that L(M) is at least L. 2. Show that L contains any string accepted by M. this implies that L is at least L(M). This way you have shown L(M) = L.
From: dhy3@cornell.edu To: Allen Weipong WangSubject: Re: CS 481: HW 1 ok, so how do you formally show that a string leads to a final state/that any string accepted by a machine is in a language. induction, i imagine, but what will the induction look like? is there perhaps, an example from the textbook or elsewhere?
From: Allen WangTo: dhy3@cornell.edu (Dennis Han Yeh) Subject: Re: CS 481: HW 1 I'm not sure what Prof. Demers has in mind for the formality, but this is what I *think* is the way to do it. Here's a bit of explanation on how to show, for example, that a string in some language leads to the the string being accepted by a machine. Generally the formality will come from defining thoroughly parts of your DFA or NFA. For example, ensure that your delta function is well defined for transitions at every node. In most cases when your proof of regularity for a language L is done in such a manner that involves constructing a machine M, the language is simple enough that you can find a nice way to represent a string in it. For example, the language consisting of all strings starting with 2 "a"s (Sigma = {a,b}) would be easily represented as aaw, where w is any string in Sigma. Now what you do is apply the delta (big Delta function) to your representative string (from L), and case-by-case strip off one character at a time from the string and follow your transitions bit by bit. Ultimately you'd like to make it so that the intersection of results from your (big Delta) transition function and the set of Final states in M is not empty. This will show that the string is accepted by M. *I imagine induction could potentially be used for steps in this, if the transition function involves lots of repetitions of some sort. However it is usually possible that you can simply follow the delta functions step by step without needing induction. For showing that a string in L(M) is in L, you do a very similar trace. Begin with the fact that a string in L(M) implies that the intersection of its Delta with F is non-null. Now you can work backwards from F, building up a string along the way, trying to reach S. When you reach S, you want the string you've built to be a string in L. Having done both of these shows that L(M) = L. (Fellow TA's, please correct me and/or add to this if you see something wrong. Thanks.)