here is what I have been working on for a week but everything I try is not worki

Question

here is what I have been working on for a week but everything I try is not working if some one could work it out and explain it to me how the program runs I would appreciate it

COSC 3302 Programming Assignment 1 (Lectures 1, 2, and 3) 1. (Membership problem for a DFA). Input: A (deterministic) finite automaton is a 5-tuple M (a, y, qo, A, 60, where a is a finite set of states, y is a finite input alphabet, go E a is the initial state, Aga is the set of accepting states, and 6 Qx Q is the transition function Note: From state q the machine will move to state 6(q, a) if it receives input symbol o. In other words, the destination state is unique hence FA is deterministic (DFA). Example Graph of a DFA Accepts all strings without two consecutive 1's. 0,1 Start Previous Previous Consecutive OK, is have does not ends in a been seen end in 1 single 1. Alternative Representation: Transition Table Final states Columns starred input symbols A A B Arrow for B A C Start state C C C Rows states The notation 5 (q, x) describes the state the FA is in after starting in state q and receiving input string x. The extended transition function 6*: axy a is defined recursively as follows: For every q E a, (q, A) J q For every q E a, every y E y, and every GEy, (q, yo)-8 (q, y), o). This just says that if you already know how to process the string y, then to process one additional symbol o, you use the ordinary transition function 8 starting from the state 6 (q, y)

Explanation / Answer

A)

package net.coderodde.dfa;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;
public class DFA {

private final TransitionFunction transitionFunction;
private final int startState;
private final Set<Integer> acceptingStates;

public DFA(TransitionFunction transitionFunction,
int startState,
Set<Integer> acceptingStates) {
this.transitionFunction =
Objects.requireNonNull(transitionFunction,
"Transition function is null.");
this.startState = startState;
this.acceptingStates =
Objects.requireNonNull(acceptingStates,
"Accepting state set is null.");
}

public boolean matches(String text) {
Integer currentState = startState;

for (char c : text.toCharArray()) {
currentState = transitionFunction.process(currentState, c);

if (currentState == null) {
return false;
}
}

return acceptingStates.contains(currentState);
}

public static void main(String[] args) {
TransitionFunction transitionFunction = new TransitionFunction();

transitionFunction.setTransition(0, 0, '0');
transitionFunction.setTransition(1, 1, '0');
transitionFunction.setTransition(0, 1, '1');
transitionFunction.setTransition(1, 0, '1');

Set<Integer> acceptingStates = new HashSet<>(Arrays.asList(0));
DFA dfa = new DFA(transitionFunction, 0, acceptingStates);

Scanner scanner = new Scanner(System.in);

while (scanner.hasNextLine()) {
String line = scanner.nextLine();

if (line.trim().equals("end")) {
break;
}

System.out.println(dfa.matches(line));
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.