Tuesday, August 30, 2016

Implement DFA ending with 'abb'

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:

  1. Make a state diagram for DFA ending with abb
  2. Trace a state-table with information from (1)
  3. 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

Most read this week!