[FrontPage] [TitleIndex] [WordIndex

Drawing FSMs

Q. JFLAP doesn’t like to make clearly visible FSMs. To which would you pay more attention: the paper version or the electronic submission? Would you want us to rewrite a paper version just so the arrows and transitional rules are more clearly visible? :)

A. I would like a version that I can see -- a picture -- in both the paper and electronic versions. This can be, e.g., a screen shot if you use JFLAP or a scan if you draw it by hand. If you use JFLAP, please *also* include the saved (runnable) JFLAP file in the e-copy version.

Q. Do we need to show our thought process behind making a certain FSM or can we just turn in an FSM as the answer?

A. You don't have to explain; you can just turn in the FSM (except for 1b if you use the multi-machine answer). If you think there's a quick-to-explain intuition and you want to add that, that's fine, but it is not necessary; it would be there as documentation to help me understand, etc. If you choose to answer 1b using two FSMs (as the question suggests), then you do need to explain "carefully and rigorously".

Question 1a

Q. Is it okay for a password to contain numbers? Should abA2 be accepted or rejected?

A. Numbers are OK; this machine should accept a password like abA2. However, the question wasn't as clear as I would have liked so that will be factored into grading. (The difference is small in any case.) 1b should, of course, accept numbers.

Q. Can my answer be a PDA?

A. Is a PDA a kind of FSM?

Q. Can I use a stack?

A. In an FSM?

Q. mumble 300 gazillion states mumble....

A. Not in my solution.

Q. Well in 1b then...

A. This is 1a. Can't you read the header? Besides, you have an alternative to drawing the full FSM for 1b. Really. It says so right in the problem set.

Question 2b

Q. For 2b the regex is: a U bb*, does that mean (a U b)b* or a U (bb*)?

A. The latter: a U (bb*)

Question 4b

Q. I’m not sure I understand this language: “The set of strings having the property that, in every prefix (i.e., every substring starting all the way at the beginning) the number of as and the number of bs does not differ by more than 2” detailed explanation by student deleted

A. Here are some examples:

aaa isn't in the language. a and aa meet the criterion, but in aaa (an improper substring, i.e., the prefix equal to the whole) the # differs by 3.

abaa is in the language. Every prefix meets the criterion: a, ab, aba, abaa.

abaaaaa is not in the language. The prefix abaaa (among others) does not meet the criterion.

Basically, if you start at the beginning and read off characters, you should never get to a point where the difference between #as and #bs is > 2.

Questions about Pumping Lemma proofs

Various Qs about pumping lemma proofs omitted, but prompting the following:

A. Recall the following about the pumping lemma:

  1. It starts with a specific (ostensibly regular) language.
  2. Therefore you know (by hypothesis) how to recognize the language with a(n) FSM.
  3. Therefore ANY sufficiently long string has the pumping property (XY*Z is in the language)
  4. But YOU don't get to pick the X/Y/Z split (beyond |XY| can't be too long and Y can't be empty).

If you're going to contradict the conclusions of the pumping lemma, you just need to find one string (in the language) that violates it, but you have to prove that there's NO way to split it. You pick the string (as concretely as you want!); you DON'T pick the split, so you have to write your proof about all possible splits of the string you picked. Sometimes you have to do this by cases.

Q. But didn't we pick X and Y in class (in the 0N 1N example)?

A. No.

In class, we picked the string: ON 1N, where N is the pumping length. That's kosher by the third statement, above.

We did NOT pick XYZ beyond observing that the XY part must be no longer than N (by the parenthetical part of the fourth statement above).

BUT, just from this, we knew that *any* choice of X and Y would still mean that the characters in X and Y were all 0s. (Why?)


2013-07-17 10:42