UMBC CMSC451, Automata Theory & Formal Languages, Fall 2005

News Archive

• [Tue Jan 03 12:11 2006]  GPG-signed report cards were sent to students who took the final exam. Instructions for verifying the GPG signature are available here.

• [Tue Dec 13 13:41 2005]  The latest weather report from the National Weather Service still says "WINTER WEATHER EXPECTED THURSDAY." Please check the UMBC Homepage for possible closure and be familiar with the Inclement Weather Policy.

• [Tue Dec 13 13:41 2005]  GPG-signed progress reports were sent to students who took Quiz 6. Instructions for verifying the GPG signature are available here.

• [Wed Dec 07 13:39 2005]  Previous posting of Question 1 of Homework 13 included Exercise 9.3.4 part a, but this question was already assigned for Homework 12. So, just do part c.

• [Tue Dec 06 18:10 2005]  The final exam (to be given on Thursday, December 15, 1-3pm), will have 7 questions on these topics:
  1. Construct an DFA/NFA that recognizes a given language.
  2. Use the pumping lemma for regular languages to show a given language is not regular.
  3. Construct a CFG for a given language or prove that a given CFG works correctly.
  4. Construct a PDA for a given language.
  5. Use the pumping lemma for context-free languages to show a given language is not context-free.
  6. TM construction.
  7. Show a given language is not decidable.

• [Tue Dec 06 18:02 2005]  Fixed Question 4 of Homework 13. The string z should be from {0,1,#}^* not {0,1}^*.

• [Tue Dec 06 09:18 2005]  Prove Question 3 of Homework 13 directly, do not use Rice's Theorem.

• [Mon Dec 05 16:23 2005]  Homework 13 has been posted.

• [Tue Nov 29 19:28 2005]  Homework 12 has been posted.

• [Tue Nov 22 10:12 2005]  Extra Credit Homework has been posted. This homework assignment is completely optional and is made available by request of several students. The assignment is worth 2 points (same as other homework assignments). You can turn in the extra credit homework any time until the last day of classes (Dec 13). However, it will not be graded until after the final exams have been graded and the cutoffs for the letter grades have been set. This way the "curve" (if any) will not be skewed by some students doing extra credit and others not.

• [Mon Nov 21 11:05 2005]  Corrected Homework 11. Question 4 should be 8.5.1, not 8.5.5.

• [Tue Nov 15 09:55 2005]  Homework 11 has been posted.

• [Fri Nov 11 13:28 2005]  A GPG-signed progress report was sent to students today. Instructions for verifying the GPG signature are available here.

• [Tue Nov 08 14:05 2005]  Homework 10 has been posted.

• [Tue Nov 01 11:50 2005]  Homework 9 has been posted.

• [Mon Oct 24 11:17 2005]  Homework 8 has been posted.

• [Wed Oct 19 10:20 2005] 

  Note added for Homework 7: When the question asks you to "design a PDA", you should give a brief high-level English description of your PDA first. (E.g., "push X whenever a 0 is read...") Then, give the transition diagram, transition table or mathematically defined transition function.

• [Mon Oct 17 16:00 2005]  Homework 7 has been posted.

• [Tue Oct 11 22:39 2005]  A GPG-signed progress report was sent to students this evening. Instructions for verifying the GPG signature are available here.

• [Tue Oct 11 12:16 2005]  Homework 6 has been posted.

• [Tue Oct 04 20:10 2005]  Homework 5 has been posted.

• [Tue Sep 27 10:57 2005]  Homework 4 has been posted.

• [Tue Sep 20 09:15 2005]  Homework 3 has been posted.

• [Tue Sep 13 11:26 2005]  Homework 2 has been posted.

• [Wed Sep 07 14:41 2005]  Slide to be used in Tuesday, September 8 lecture: Slide 1. (We'll critique this write up.)

• [Tue Sep 06 09:55 2005]  Homework 1 has been posted.

• [Wed Aug 31 15:55 2005]  Our TA, Suresh Purini, will hold office hours on Mondays and Wednesdays from 3:30pm - 4:30pm. Details are on the contacts page.

• [Thu Aug 18 16:00 2005]  Note: Be aware of the schedule of in-class quizzes listed in the syllabus!
  The first quiz is on Thursday, September 22.

• [Thu Aug 18 15:55 2005]  Web page up.