UMBC CMSC451-01, Automata Theory, Fall 2023

News Archive

• [Mon Dec 04 12:07 2023]   Fixed typo in Homework 13. In Question #1, M₂ on input ε should print out < M₁>, rather than < M₂>,

• [Thu Nov 30 22:50 2023]   Homework 13, Due Thu 12/07/23   [Submit]

• [Tue Nov 21 16:40 2023]   Two classic textbooks in recursive function theory. These are quite dense. I have not kept up with more modern texts, but a quick internet search did not uncover any:
  • Theory of Recursive Functions and Effective Computability, Hartley Rogers, 1967. (ISBN: 978-0262680523).
  • Recursively Enumerable Sets and Degrees, Robert I. Soare, 1987. (ISBN: 978-3540152996 ).

• [Tue Nov 21 16:30 2023]   Here's the final Perl program shown in class that prints itself. You may have to change the first line depending on where Perl lives on your system. The earlier versions are in this directory. #!/usr/bin/perl $B = '$slash = "\x5C" ; $C = $B ; $C =~ s/\'/$slash\'/g ; print "#!/usr/bin/perl\n\n" ; print "\$B = \'$C\' ;\n" ; print "$B\n" ;' ; $slash = "\x5C" ; $C = $B ; $C =~ s/'/$slash'/g ; print "#!/usr/bin/perl\n\n" ; print "\$B = '$C' ;\n" ; print "$B\n" ;

• [Mon Nov 20 12:15 2023]   No office hours this Wednesday, November 22.

• [Mon Nov 20 12:15 2023]   Fixed typo in Homework 12. Question 1 should say "Show that L ≤_m P" (instead of C).

• [Thu Nov 16 23:05 2023]   Homework 12 posted. Due Thu 11/30/23 (after Thanksgiving)   [Submit]

• [Thu Nov 09 16:40 2023]   Homework 11 posted. Due Thu 11/16/23   [Submit]

• [Thu Nov 02 18:18 2023]   Homework 10 posted. Due Thu 11/09/23   [Submit]

• [Wed Oct 25 15:00 2023]   Homework 9 posted. Due Thu 11/02/23   [Submit]

• [Tue Oct 24 22:15 2023]   Fixed typo (past-o) in Homework 8. In Questions 1 & 2, it should say to use the pumping lemma to show that the language is not context-free (instead of not regular).

• [Wed Oct 18 18:05 2023]   Homework 8 posted. Due Thu 10/26/23   [Submit]

• [Thu Oct 12 00:40 2023]   Homework 7 posted. Due Thu 10/19/23   [Submit]

• [Wed Oct 04 21:15 2023]   Homework 6 posted. Due Thu 10/12/23   [Submit]

• [Thu Sep 28 17:15 2023]   Fixed typo in Homework 5. Now at version 1.1.

• [Wed Sep 27 17:40 2023]   Homework 5 posted. Due Thu 10/05/23   [Submit]

• [Thu Sep 21 17:45 2023]   Minor change to Homework 4. The language in Question #5 was changed to D from B since we already have a B in Question #3.

• [Wed Sep 20 17:35 2023]   Homework 4 posted. Due Thu 09/28/23   [Submit]

• [Thu Sep 14 16:55 2023]   Homework 3 posted. Due Thu 09/21/23   [Submit]

• [Wed Sep 06 17:30 2023]   Homework 2 posted. Due Thu 09/14/23   [Submit]

• [Mon Sep 04 10:30 2023]   Here are the links for the online office hours:
  • Prof. Chang: https://meet.google.com/ads-owoo-jgi
  • TA Budhini Amaraneni: https://meet.google.com/yqb-vnya-brk
  These links are also on the contacts page and embedded in the class calendar events.

• [Mon Sep 04 10:30 2023]   Our TA Budhini Amaraneni will hold office hours on Mondays and Wednesdays 11am to 12pm online. (Details to follow.) The contacts page and syllabus (in PDF) have been updated.

• [Wed Aug 30 22:45 2023]   Homework 1 posted. Due Thu 09/07/23   [Submit]

• [Fri Aug 25 22:45 2023]   The course description and schedule is also availalbe in PDF.

• [Fri Aug 25 22:45 2023]   Web page up.