Implementing NFAS in a spreadsheet
2005; Consortium for Computing Sciences in Colleges; Volume: 20; Issue: 3 Linguagem: Inglês
ISSN
1937-4771
Autores Tópico(s)Spreadsheets and End-User Computing
ResumoThis paper describes a novel translation of a Nondeterministic Finite Automation (NFA) into a spreadsheet suitable for a program such as Microsoft Excel or Gnumeric. This translation can help students understand the structure of an NFA and provide a simple means to animate the NFA's actions to determine if it accepts an input string.A student can manually enter the spreadsheet cells corresponding to a particular NFA using only simple arithmetic expressions and formulas that involve the if function. For a complex NFA with many states and transitions, a manual entry process can be quite time-consuming and error-prone. We have written a Perl program that translates a NFA description given as an input text file into an output text file format that can be imported directly into commonly-available spreadsheet programs.The student can use the spreadsheet dynamically to play with the NFA: by giving it strings to accept/reject; by changing the set of accept states; and by changing the symbols that are associated with state transitions.
Referência(s)