DFA java simulation

Job Description:

For this task you need to implement a deterministic finite automaton (DFA) abstract data type. Recall that a DFA is a quintuple (Q, Σ, δ, q0, F ): Q is a non-empty, finite set of states; Σ is non-empty, finite set of symbols (an alphabet); δ : Q × Σ −→ Q is the transition function; q0 ∈ Q is the start state; and F ⊆ Q is the set of accept states. A DFA accepts a string w = w1w2 ···wn ∈ Σ∗ if there is a sequence r0,r1,...,rn of states such that (i) r0 = q0, (ii) rn ∈ F, and (iii) δ(ri,wi+1) = ri+1, for every 0 ≤ i < n.

2 Requirements

• We make the following assumptions for simplicity.

a) The alphabet Σ is always the binary alphabet {0,1}.

b) The set of states Q is always of the form {0,...,n}, for some n ∈ N.

c) The start state is always state 0.

• You should implement two functions: dfa and run.

• dfa (which could be a class constructor) takes one parameter which is a string description of a DFA and returns (or constructs) a DFA instance as per the description.

• A string describing a DFA is of the form P#S, where P is a prefix representing the transition function δ and S is a suffix representing the set F of accept state.

• P is a semicolon-separated sequence of triples of states; each triple is a comma-separated sequence of states. A triple i,j,k means that δ(i,0) = j and δ(i,1) = k.

• S is a comma-separated sequence of states.

• For example, the DFA for which the state diagram appears below may have the following string representation.

0,0,1;1,2,1;2,0,3;3,3,3#1,3

1

Compétences : Java

Nº du projet : #33115859