Automata and Formal Languages 2010/11

If you have fixed your programming group write me (jan.kretinsky AT in.tum.de) an email with the subject AFL-SVN and a body containing your names and student-id numbers and I will reply with your login and password for your svn. By January 30 you should upload your final solution to this svn - https://svn.model.in.tum.de/stud/[your login]

Here you can find (compressed in .rar) the following data:

• antlrworks-1.4.jar: a tool available at antlr.org to create grammars and generate parsers out of them
• antlr-3.2.jar: library you need to use the parser
• junit-4.8.2.jar: library for testing

  for Java:
  

• lexer class and parser class
• classes showing how to use the parser and test it on sample formulae
• sample formulae 1 and 2
• the grammar for PA and the list of its tokens

  for C++:
  

• lexer source and header and parser source and header
• classes showing how to use the parser on the sample formulae
• sample formulae 1 and 2
• the grammar for PA and the list of its tokens

A list of examples and its solutions is accompanied by time in seconds that my unoptimized programme needed at my desktop / at halle.in.tum.de

Basic examples (all took below 0.5 s at my desktop and around 1 s at halle):

• an example from the Skript and its solution
• solutions to sample formulae 1 and 2
• yet another example formula5.txt and its solution formula5.txt.dotty (and former incorrect solution formula5.txt.dotty-old)
• and a new example formula6.txt and its solution formula6.txt.dotty (try to understand this formula and its solution, you can then easily generate more examples for your testing by yourself)

Advanced examples (mainly with more variables and nested quatification alternation):

• formula3.txt and its solution formula3.txt.dotty (21 s / 26 s) (and former incorrect solution formula3.txt.dotty-old)
• formula4.txt and its solution formula4.txt.dotty (25 s / 32 s) (and former incorrect solution formula4.txt.dotty-old)
• formula7.txt and its solution formula7.txt.dotty (61 min / 74 min)
• formula8.txt and its solution formula8.txt.dotty (2 min 30 s / 2 min 50 s)
• formula9.txt (java.lang.OutOfMemoryError: Java heap space after 440 min)