CS311 Formal Language and Automata Programming Assignment

CS311 Formal Language and Automata Programming Assignment: DPDA Simulation

Problem Statement

Write a program that allows a user to enter a description of a deterministic pushdown automaton followed by a sequence of input symbols. After each input symbol the program will display the current state and the contents of the stack. At the end of input, the program will indicate whether the dpda ended in an accepting state.

Details

The states for your PDA will be labeled with the integers 0, 1, 2, ..., n. State 0 will be the start state. The alphabet will consist of single printable ASCII characters other than the period character.

Input consists first of an integer specifying the number of states, white space, and then a string containing the alphabet symbols for the dpda. The stack alphabet will be defined implicitly by the transition function with dollar sign, '$', as the initial symbol on the stack. The transition function is coded on a series of lines as follows. Each line contains the arguments and results for one evaluation of the transition function. Each entry consists of five components, the current state, the input symbol, the symbol on top of the stack, the new state, and the string of symbols to push onto the stack, separated by white space. If the nothing is to be pushed onto the stack, the entry is the period, '.'. The entries may be coded in any order. Omitted entries lead to a trap state. A line containing -1 indicates the end of the transition function entries. The transition function values are followed by a line with a list of numbers specifying the final states ending with -1 as a sentinel.

Sample DPDA description for aⁿbⁿ

4                  number of states = 4
ab                 alphabet, {a, b}
0 a $ 1 A$         transition d (0,a,$) = (1,"A$")
1 a A 1 aA         transition d (1,a,A) = (1,"aA")
1 a a 1 aa         transition d (1,a,a) = (1,"aa")
1 b a 2 .          transition d (1,b,a) = (2, ?)
1 b A 3 .          transition d (1,b,A) = (3, ?)
2 b a 2 .          transition d (2,b,a) = (2, ?)
2 b A 3 .          transition d (2,b,A) = (3, ?)
-1                 end of transition function
1 3 -1             final states: {1, 3}

After the DPDA description has been entered, the program will display the start state and initial stack. The program will then repeatedly prompt for an input character and display the new current state followed by the contents of the stack as a string. This process continues until end of input or until the DPDA gets stuck. At this point print a message indicating whether the string was accepted or not.

Sample Execution on string aaaabbbb

Current status 0:$, Enter input: a
Current status 1:A$,	Enter input: a
Current status 1:aA$,	Enter input: a
Current status 1:aaA$,	Enter input: a
Current status 1:aaaA$,	Enter input: b
Current status 2:aaA$,	Enter input: b
Current status 2:aA$,	Enter input: b
Current status 2:A$,	Enter input: b
Current status 3:$,	Enter input: .
String accepted.

The program may include prompts but may not require any input other than that specified.

Deliverables:

Source code with appropriate comments
A report with screen shots for one case of accepting a string, and one case of rejecting a string.

Lost Password