This is a program in Java which maps the DFA for input string where the ending substring must be 'abb' to be accepted. Since definition of DFA is a trivial topic for this question, any pre-requisite information about DFA that you might need is available at this site.
Procedure:
SOURCE CODE:
when string is accepted in DFA:
Procedure:
- Make a state diagram for DFA ending with abb
- Trace a state-table with information from (1)
- Write a program to emulate the behavior of given DFA with the rules provided by (2)
If you need further elaboration in this topic^(i.e. Procedure), please drop a comment and we'll post DFA state-diagram and state-table also.
SOURCE CODE:
public class DfaFinder {
public static void main(String[] args) {
// Implement DFA ending with abb
String state_now="q0";
Scanner sc= new Scanner(System.in);
String string= sc.nextLine();
HashMap a = new HashMap();
HashMap b = new HashMap();
a.put("q0","q1");
a.put("q1","q1");
a.put("q2","q1");
a.put("q3","q1");
b.put("q0","q0");
b.put("q1","q2");
b.put("q2","q3");
b.put("q3","q0");
System.out.print("Tracing DFA..\nstart:q0");
for(int i=0;i<string.length();i++){
if(string.charAt(i)=='a'){
state_now=(String)a.get(state_now);
}
else if(string.charAt(i)=='b'){
state_now=(String)b.get(state_now);
}
System.out.print("-->"+state_now);
}
if(state_now.equals("q3")){
System.out.println("\nConclusion: This string is accepted in DFA");
}
else{
System.out.println("\nConclusion: This string is not accepted in DFA");
}
}
}
OUTPUT:when string is accepted in DFA:
when string is rejected in DFA:
If you have any doubt, please feel free to inquire.
Blogger Comments:
Emoticon Emoticon