Моделирование конечного детерминированного автомата по этим данным
У меня есть этот входной файл:
2
3 2 1
ab
1 0
2 0
2 0
2
0 3
abaa
aab
aba
3 3 2
ade
0 1 2
1 2 0
2 1 0
1 2
2 2
a
de
Первая строка представляет количество тестовых случаев.
Каждый тестовый пример начинается с 3 целых чисел, первое - это номер состояния автомата, затем - количество символов в алфавите и затем число конечных состояний.
Следующая строка - алфавит. Символы появляются вместе.
То есть's количество строк, равное количеству состояний, которые описывают функцию перехода. Первая строка этой группы строк представляет функцию перехода для первого состояния в автомате (qo), первый элемент представляет состояние, которое 's достигается, когда первый символ в алфавите переходит в это состояние, и так далее. У меня были проблемы с пониманием этого из первоначальной постановки задачи. Это самый простой способ, которым ямы пришли посмотреть на это:
Линии:
1 0
2 0
2 0
равны:
AlphabetSymbol0 AlphabetSymbol1
State0 State1 State0
State1 State2 State0
State2 State2 State0
То есть's линия, которая говорит, какие конечные состояния для автомата.
Затем идет строка, в которой говорится, какое начальное состояние и сколько поступит входных строк.
Затем идут строки с входными строками.
Вывод этой программы должен быть:
Case #1:
accept 2
reject 0
reject 1
Case #2:
accept 2
reject 0
Должно быть указано, принята строка или отклонена и в каком состоянии она завершилась.
Пока что яМы только закодировали работу со входом.
Я неНе знаю, как было бы наиболее удобно представлять автомат. Должен ли я создать класс Graph? Должен ли я просто использовать массивы? Какую логику я бы применил к массивам?
ИЗМЕНИТЬ ЭТОТ КОДЕКС ЯVE ПРОИЗВОДИТ СЛЕДУЮЩУЮ МИХАИЛ БОРГВАРДТСОВЕТ. Переходы работают, но я неЗНАЕТЕ, ПОЧЕМУ СТРОКА НАСТУПАЕТ НА СОСТОЯНИИ 0, КОГДА БУДЕТ ОБРАБОТАНО. **Я'
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package afd;
import java.io.*;
import java.util.*;
/**
*
* @author Administrator
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
// TODO code application logic here
FileReader fr = new FileReader("E://Documents and Settings//Administrator//My Documents//NetBeansProjects//AFD//src//afd//dfa.in");
BufferedReader br = new BufferedReader(fr);
String firstLine= br.readLine();
String [] firstLineSplitted = firstLine.split(" ");
/*debug*/
System.out.println("firstLine is " + firstLine);
int numberOfTestCases = Integer.parseInt(firstLine);
for (int indexOfTestCases =0; indexOfTestCases < numberOfTestCases; indexOfTestCases++ ){
String caseStartLine = br.readLine();
/*debug*/
System.out.println("caseStarLine is " + caseStartLine);
String [] caseStartLineSplitted = caseStartLine.split(" ");
int numberOfStates;
int numberOfAlphabetSymbols;
int numberOfFinalStates;
numberOfStates = Integer.parseInt(caseStartLineSplitted[0]);
numberOfAlphabetSymbols = Integer.parseInt(caseStartLineSplitted[1]);
numberOfFinalStates = Integer.parseInt(caseStartLineSplitted[2]);
Automaton automaton = new Automaton();
automaton.setAllStates(numberOfStates);
// automaton.size = numberOfStates;
// automaton.numberOfAlphabetSymbols = numberOfAlphabetSymbols;
// automaton.numberOfFinalStates = numberOfFinalStates;
//Automaton a = new Automaton(numberOfStates);
String alphabetLine = br.readLine();
System.out.println("alphabetLine is " + alphabetLine);
automaton.setAlphabet (alphabetLine);
// automaton.alphabetSymbols =new StringBuffer(alphabetLine);
for (int indexOfStates = 0; indexOfStates < numberOfStates; indexOfStates++){
String transitionsLine = br.readLine();
/*debug*/
System.out.println("transitionsLine is " + transitionsLine);
automaton.setTransitions(indexOfStates,transitionsLine);
/*String [] ijLineSplitted = ijLine.split(" ");
int i = Integer.parseInt(ijLineSplitted[0]);
int j = Integer.parseInt(ijLineSplitted[1]);
*/
}
String finalStatesLine = br.readLine();
/*debug*/
System.out.println("finalStatesLine is " + finalStatesLine);
String finalStatesLineSplitted [] = finalStatesLine.split(" ");
automaton.markFinalStates(finalStatesLineSplitted);
String initialStateAndNumberOfStringsLine = br.readLine();
/*debug*/
System.out.println("initialStateAndNumberOfStringsLine is " +initialStateAndNumberOfStringsLine);
String [] splittedInitialStateLine = initialStateAndNumberOfStringsLine.split(" ");
int initialState = Integer.parseInt(splittedInitialStateLine[0]);
int numberOfStrings = Integer.parseInt(splittedInitialStateLine[1]);
automaton.markInitialState(initialState);
for (int stringIndex =0; stringIndex