Courses/CS 386/Fall 2009

From CSWiki

Jump to: navigation, search

Contents

 
  • Meeting times and place
Tuesdays: ET 210. 1:30PM - 3:10PM.
Thursdays: Watch video.


  • Grading
The nominal grade in this class is based 33.33% on each of two mid-terms and 33.33% on a final. It will be adjusted according to these qualities.


  • Process
There will be no class meetings Thursdays. You are expected to watch the course video and do the homework problems. Use the discussion page to ask (and answer) questions. We will then meet in class each Tuesday. We will discuss your questions after which there will be a quiz. The quizzes will count 66.66% of the course grade.


  • Textbook:
Peter Linz (2006) An Introduction to Formal Language and Automata, 4e.
Please bring the text book to class.


  • Software:
JFLAP web site
"JFLAP" (jar) (upload page)
JFLAP Tutorial


  • HTML symbols
Character Entity References Defined in HTML 4.0
Entities
Entities for accented characters, accents, and other diacritics from Western European Languages
Character Entity Html Reference
HTML Entity Reference.



[edit] Week 1. September 24 & 29

Watch Sep 24.
Class Sep 29.
  • Textbook: Chapter 1: [1.1 and 1.2]. Exercise answers and hints pp 357 - 368.
  • Homework:
    • pp 14-15: 12, 19, 24, 27, 29;
    • pp 27-29: 7, 8, 9, 11 a, b, c, 18 b, d,

[edit] Week 2. October 1 & 6

Watch Oct. 1.
Class Oct 6.
  • Textbook: Chapter 2. Finite Automata.
    • 2.1. p 47/368. 2.c, 5.a, 7.a, 7.d, 9.a, 9.d, 14.
    • 2.2. p 55/371. 3, 8, 16, 18.
    • 2.3. p 62/372. 7, 8, 15.
  • Homework:
    • 2.1. 2.e, 7.b, 9.f, 17 (Given M construct M' so that L(M') = L(M) - {λ}),
    • 2.2. 11, 14.
    • 2.3. 1, 5, 6, 12.

[edit] Week 3. October 8 & 13

Watch Oct. 8
Class Oct. 13
  • Textbook: Chapter 3. Regular expressions.
    • 3.1. p. 71. (Definition of Regular Expression. p. 72.) p. 376. 2, 6(a), 6(c), 16(c), 17(c), 20(c), 23,
    • 3.2. p. 77. (Regular expressions and nfa's are equivalent.) p 377. 3, 4(a), 8(a), 10(b), 16(a).
  • Homework:
    • 3.1. 16(a), 17(a), 17(b), 17(e), 20(b), 20(d).
    • 3.2. 2, 4(d), 9, 17.

[edit] Week 4. October 15 & 20. First midterm.

Watch Oct. 15
Class Oct. 20
  • Textbook: Chapter 4. Properties of regular languages.
    • 4.1. p. 100 (Regular languages are closed under union, intersection, complement, concatenation, star, and reversal) p. 381. 2(a), 12, 16, 18.
    • 4.2. p. 111. (p. 112: decision questions). p. 382. 1, 2, 5, 12.
    • 4.3. p. 114. (Pumping Lemma. p. 115.). p. 382. 4(a), 4(e), 5(a), 14, 15(a), 15(b), 19(a), 21.
Pumping Lemma. If L is an infinite Regular language, then there is an m (typically related to the number of states in the fsa that accepts L) so that for every w in L where |w| > m, w can be decomposed into w = xyz so that |xy| <= m, |y| >= 1, and x y*z is also in L.
  • Homework:
    • 4.2. 3, 6, 7, 14.
    • 4.3. 4(d), 4(f), 5(b), 20, 24, 26.


[edit] Test on Finite Automata.

Submit all work through CSNS.

The test is open book and open notes. You may also access the Internet. You may not help each other.

Submit three separate files, one for each question.

Files submitted after 3:10 will be penalized 5 points for each minute late.

Each question is worth 33 points. One point is free.

[edit]

  1. Create an nfa for the language L(R) defined by the regular expression R = (00 + 01 + 000)* . Submit a JFLAP loadable file (.jff) containing your nfa. To generate a .jff file use the Save or Save As option from the JFLAP file menu.

    Most people got this one right. Here's a standard answer. Image:386-Fall-2009-nfa.png

    2. [edit]

  2. Create a dfa for the same language. Submit a JFLAP loadable file (.jff) containing your dfa.

    This was a bit harder. Here's a minimal answer. Notice that a 1, if it comes at the end of a string that is accepted, brings the dfa back to its start state. That will be a useful observation for the next question.
    Image:386-Fall-2009-dfa.png

    3. [edit]

  3. Consider the complement of L(R). If it's regular, submit a text file (.txt) containing a regular expression for it. If it's not regular, submit a text file (.txt) containing the answer "Not regular."

    This was the most difficult. First of all, the complement of any regular language is regular. So the complement of L = (00 + 01 + 000)* is regular.
    One way to get the answer is to ask which strings aren't in L, i.e., which strings are in L'. The string 0 and any string beginning with 1 are in L'. So far we have the following.
    L' = 0 + 1(0+1)* + ...
    What other strings are not in L? Any string of 0's of length 2 or more is in L. All of those substrings of 0's are terminated by 1's. So the question comes down to what can come between a pair of 1s. The only strings beginning and ending in 1 that are not possible are 11 and 1001. That gives us the following.
    L' = 0 + 1(0+1)* + (0+1)*(11 + 1001)(0+1)* + ...
    Finally, how do strings in L' end? They can end in 1, except for cases considered earlier. What about ending in 1 followed by a sequence of 0's? How many 0's would prevent a string from belonging to L? The ending 10 is impossible. All other sequences of terminal 0's are possible. That gives us the following.
    L' = 0 + 1(0+1)* + (0+1)*(11 + 1001)(0+1)* + (0+1)*10
    L' = 0 + 1(0+1)* + (0+1)*[(11 + 1001)(0+1)* + 10]
    L' = 0 + 1(0+1)* + (0+1)*[1(λ + 00)1(0+1)* + 10]

    Another approach is to generate a dfa for L', the complement of L and use that to get the answer. Here's a dfa for L'. It was generated by adding the trap state to the dfa for L and then switching the final and non-final states.
    Image:386-Fall-2009-dfa-complement.png
    What does it accept? As before it accepts any string starting with 1. So again we can start with this.
    L' = 1(0+1)* + ...
    What else? What about strings that start with 0? That amounts to asking for paths from q1 to either q1or q4.
    L' = 1(0+1)* + 0 ...
    From q1 we can get back to q1 with (10 + 000*10) = (λ + 000*)10.
    L' = 1(0+1)* + 0[((λ + 000*)10)*(λ + <q1 to q4>)]
    We can get from q1 to q4 with 01 + 000*11 = 0(λ + 00*1)1. This produces the following.
    L' = 1(0+1)* + 0[((λ + 000*)10)*(λ + 0(λ + 00*1)1)]

[edit] Test scores and projected grades

A  : 100, 99, 97, 92, 92,
B  : 87, 82,
C  : 74, 72, 60, 59, 59, 59, 49, 49, 47, 44, 44,
D  : 36, 36, 36, 31, 26,
F  : 8.

Anyone with a grade of C–, D, or F who wants that as their final grade, send me an email message.

[edit] Week 5. October 22 & 27

Watch Oct. 22
Class
  • Textbook: Chapters 5 (Context Free Grammars) & 7 (Pushdown Automata).
    • 5.1 (Context Free Grammars) p 133/384. 7.a, 7.d, 13.a, 20, 23,
    • 5.2 (Ambiguity) p 145/385. 6.
    • 5.3 (CFG for programming languages) The expression grammar: pp. 146 & 142.
    • 7.1 (Nondeterminstic PDAs) Definition p. 177. 183/389. 4.a, 4.b, 4.g
    • 7.2 (nPDAs and CFLs) p. 195/391. 3, 4.
  • Homework:
    • 5.1 (Context Free Grammars) p 133. 7.e, 7.f, 8.c, 13.c, 21, 24,
    • 5.2 (Ambiguity) p 145. 8, 12.
    • 5.3 (CFG for programming languages) The expression grammar: Generate a parse tree for: a*b + c and a*(b+c).
    • 7.1 (Nondeterminstic PDAs) Definition p. 183. 4.b, 4.c, 4.d, 4.i.
    • 7.2 (nPDAs and CFLs) p. 195. 5, 6.

[edit] Week 6. October 29 & November 3

Watch Oct. 29

[edit] Content

Theorem 7.1 (p 186). Last time, we didn't talk very much about how an npda recognizes a CFG. The basic idea is that the npda uses its stack for the unexpanded part of the derivation string.

Theorem 8.1 (p 206) The pumping lemma for CFGs. Look at the diagram on p 207. Basically the argument is parallel to that for dfa's. Any parse tree deeper (higher) than the number of non-terminals in the grammar must repeat a non-terminal. That non-terminal can be pumped.

Exercises 8.1 p 212/393. 3 (the same w), 7f (can't compare three things, just 2), 8b (the order of a's and b's prevents comparing the a's before the b's), 10 (It is context free because all one needs is to guess the non-matching symbols! Since it is non-deterministic, will guess right!)

Section 8.2 Theorems 8.3, 8.4, 8.5, 8.6, 8.7, p 214 ... To prove these it is useful to recall Theorems 6.2 and 6.3, elimination of useless and λ productions. But see p. 219 before the exercises for properties that aren't decidable, e.g., whether two context-free grammars define the same language.

Exercise 219/394. 5.

[edit] Homework

  • p. 212. 8 a, c, d, f, g. (For each, answer whether it is CF and provide a justification for your answer.)
  • p. 219. 7, 12, 14, (For most of the preceding, you can probably use {anbncn} as an example of a language this is not CF.) 22, 23.

[edit] Week 7. November 5 & 10. Second midterm (cumulative).

video

[edit] Midterm II.

For each of the following languages answer the following questions.

  1. Is it regular? If so, create and submit a dfa using JFLAP.
  2. Is is context free? If so, create and submit a text file containing a CF grammar for it. (Use S as the start symbol.)

In both cases, if the langauge is not regular or context free, submit a text file with the words "Not regular." or Not context free."

  1. { (ab)n (ab)m : n > m > 0}
  2. { wn wm : w in {a, b}* ; n > m > 0}
    For each string in the language w is the same each time it occurs. But w may be different from one string in the language to another.
  3. { (aba)n (bab)m : n > m > 0}
  4. { an bm : n mod 4 == m mod 3}

Submit a separate file for each part. Submit your files through CSNS. There will be 8 files in all; 2 for each language. The files should be labelled: 1a, 1b, 2a, 2b, 3a, 3b, 4a, 4b.

Each part is worth 12.5 points. Answers submitted after 3:10 will lose 5 points per minute late.

Open book; open notes; open Internet. No helping each other. If you use one of the preceding resources, cite it, explain what it says, and explain your use of it.

[edit] Midterm II. Answers.

  1. { (ab)n (ab)m : n > m > 0 }
    1. Regular. The trick is that the language can also be represented as { (ab)n : n > 2 }.
      { (ab)n (ab)m : n > m > 0 } = { (ab)n (ab) : n > 1 } = { (ab)n : n > 2 }. Here's a dfa for it.
      Image:ababab.png
    2. Since it's regular, it's also context free. Here is a grammar. Generate at least three "ab" sequences. 
       S → abab A
 A → ab A | ab
  2. { wn wm : w in {a, b}* ; n > m > 0}
    For each string in the language w is the same each time it occurs. But w may be different from one string in the language to another.
    1. Not regular.
    2. Not context free.
    This is like { w w : w in {a, b}* } only worse.
  3. { (aba)n (bab)m : n > m > 0}
    1. Not regular.
    2. Context free. This is like { an bm : n > m > 0}, which we know is context free. Here is a grammar. 
      S → aba X
X → aba X bab | aba X | ababab

      We did something very much like this on the board immediately before the test. It stayed on the board throughout the test!

  4. { an bm : n mod 4 == m mod 3}
    1. Regular.
      Image:a^nb^m.png
      The "a" states keep track of the number of a's mod 4. The "needs x b's" states keep track of the number of b's needed to make n mod 4 == m mod 3.
    2. Context free. Here is a grammar. 
      S → aaaa S | S bbb | λ | a b | aa bb

[edit] Grades

Instead of counting each part 12.5 points, everyone got 20 points as a floor. Each part was then worth 10 points.

C: 70, 70, 69, 66, 66, 61, 60, 59, 54, 53, 51, 51, 50, 50, 45, 45,
D: 38, 38, 35, 35, 33, 30.

[edit] Grade adjustment

If your grade is G it will become max(G, 2 x G - 50)

Adjusted grades.

A–: 90, 90
B+: 88
B–: 82, 82
C  : 72, 70, 68, 58, 56, 52, 52, 50, 50, 45, 45,
D  : 38, 38, 35, 35, 33, 30.

[edit] Grades to date and final grade option

Using this formula 

0.5 * (Midterm_1 + max(2*Midterm_2 - 50, Midterm_2))

these are the numeric and projected grades to date.

B  : 87, 83.5
B–: 82
C+: 79
C  : 75, 72, 70.5, 68,5, 62, 60.5, 58.5, 58, 55.5, 53.5, 50.5, 48.5, 47
D  : 39.5, 37, 34.5, 32

This number will be weighted with the final on a 2-to-1 basis for a final number. A final course grade will be derived from that number.

However, I will give you the option of not taking the final in which case your final grade in the course will be 

min(Current projected grade, C)

In other words, if you have a projected grade of C or better and don't take the final, your course grade will be C. If you take the final, your course grade may be worse that your current projected grade.

[edit] Week 8. November 12 & 17

No video, but look at this page.
  • Textbook: Chapter 9. Turing machines.
  • Homework:
    • Section 9.1. Example 9.8 (p232), Exercises (p 236) 8 (Note that there is no middle marker), 9, 11.b, 11.d, 11.e. Also construct a Turing machine that accepts the complement of the language in exercise 8. (Use JFLAP for these. Construct your machine and run some examples.)


Watch Nov. 12

  • Textbook: Sections 10.2, 10.3, 10.4. More Turing machines, including a universal Turing machine.
  • Homework: Section 10.3 (p. 266) 4; Section 10.4 (p 270) 5, 7, 9. Sketch out the answers at the same level of detail as the answers in the back of the book.


Video for 11/17

[edit] Week 9. November 19 & 24

Watch Nov. 19
Video for Nov 24
  • Textbook: Section 11.1. Recursive and recursively enumerble languages.
  • Homework: TBD.

[edit] Week 10. December 1 & 3

  • Textbook: Section 12.1 Undecidability.

Even though the previous Thursday is a holiday, please watch the video and prepare for December 1 as a regular Tuesday. December 3 will be available for review.

[edit] Week Finals. December 8

Retrieved from "http://cs.calstatela.edu/wiki/index.php/Courses/CS_386/Fall_2009"