1. (Membership problem for a DFA). Input: A (deterministic) finite automaton is
ID: 3850804 • Letter: 1
Question
1. (Membership problem for a DFA). Input: A (deterministic) finite automaton is a 5-tuple M (Q, 3, go, A, 5), where Q is a finite set of states, is a finite input alphabet, qo e Qis the initial state, AgQ is the set of accepting states, an Q x Q is the transition function. Note: From state q the machine will move to state o(q, G) 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 Consecutive Previous string OK, string ok, 1's have does not ends in a been seen. end in 1 single 1.Explanation / Answer
import java.util.Scanner;
public class TestDFA {
public static void main(String[] args) {
//define a DFA that accepts
//strings without 2 consecutive 1's
String[] q = {"A","B","C"};
char[] sigma = {'0','1'};
String q0 = q[0];
String A = q[1];
Scanner sc = new Scanner(System.in);
System.out.println("Enter the string: ");
String input = sc.next();
//transition table
for(int i=0;i<input.length();i++){
char c = input.charAt(i);
//apply transitions
switch(q0){
case "A":
if(c==sigma[0]) q0 = q[0];
if(c==sigma[1]) q0 = q[1];
break;
case "B":
if(c==sigma[0]) q0 = q[0];
if(c==sigma[1]) q0 = q[2];
break;
case "C":
if(c==sigma[0]) q0 = q[2];
if(c==sigma[1]) q0 = q[2];
break;
}
}
if(q0.equals(A))
System.out.println("String accepted");
else
System.out.println("String not accepted");
sc.close();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.