2/17/2023 0 Comments Automaton simulator![]() There are three possible outcomes from this process: DPDA, NPDA, INVALID. Upon reading the machine description file, your program should validate it. ![]() ![]() Note that the mere presence of an epsilon in a transition rule does NOT necessarily make the machine nondeterministic nondeterminism is present only if there is at least one point in the machine where at least two distinct options exist for going forward. Since the space character is in the input and stack alphabets, it might be included in the transition rules as a literal character.Ī nondeterministic machine description has multiple transition rules for the same state/input/stack combination.Your program needs to accommodate both possibilities. The end of each line is denoted by a newline sequence, which could be either a LF or a CR/LF pair, depending on the operating system used.State, input symbol, pop symbol, new_state, push symbolĮxcept as noted here, there will not be any whitespace in the file. Line #2+: One transition rule per line in the form: Line #1: Curly-brace enclosed, comma-separated list of accept states. With this common framework, the description file contents are as follows: Recall that attempting to read an empty stack is not allowed, thus this equates to a transition to the non-accepting trapstate.If a transition rules is not defined for a given combination of state, input character, and stack character, then it is inferred that the transition is to the non-accepting trap state (state 255).Δ: Transition function ( Q x Σ ε x Γ ε → Q x Γ ε ) The “nominal” stack alphabet for the machine consists of those characters from the official stack alphabet for which at least one transition rule is defined.For convenience, the “official” stack alphabet is the same as the input alphabet.The “nominal” input alphabet for the machine consists of those characters from the official input alphabet for which at least one transition rule is defined.Also note that the space character (ASCII code 32 (0x20)) IS a printing character. Note that the ASCII code for the back tick isĩ6 (0圆0). (`), which serves as an ‘epsilon’ character. The “official” input alphabet consists of all of the printing characters (as defined by the C standard library function isprint()) except the grave accent (a.k.a.State 255 is an inferred non-accepting trap state.The states need not be numbered sequentially.The “nominal” set of states are those states that are reachable from the start state.The “official” set of states are 0 through 255, inclusive. ![]() Recall that the formal description of a PDA is M =. Input file: strings.txt (the same file for all machines) Machine Description File – basename.fa This should allow you to write a wrapper program that processes all of the machines in a single run. The first machine will have a base name of m00 and the remaining machines will be numbered sequentially. So that all of the files can be in the same directory, the following naming conventions will be used:īase name: mxx where xx is a two digit number. To avoid operating-specific case-sensitivity issues, all filenames will be all lowercase. However, all students will receive the same set of machines, so undergraduates will need to be able to determine whether a machine is deterministic or not. Undergraduate students are only responsible for being able to process deterministic machine descriptions, while graduate students must also be able to process nondeterministic machine descriptions. Each string that is accepted by the PFA will be echoed to a text file in addition each machine will have a log file prepared containing specific pieces of information. In this project you will write a program that will read a simplified description of a pushdown automaton, validate it, and then simulate it on each string read from an input text file.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |