Friday, September 2, 2016

Implement DFA that accepts only 'int' or 'integer'

This is a program in Java which maps the DFA for input string where the string must be 'int' or 'integer' to be accepted. It is also an excellent example for DFAs with deadends. 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 accepting 'int' or 'integer'

    Edit: I seem to have made a small mistake while making the state diagram. q3 and q7 are actually FINAL STATES and those two states should have double circle instead of single one :)

  2. Trace a state-table with information from (1)
    i n t e g r
    q0 q1 q8 q8 q8 q8 q8
    q1 q8 q2 q8 q8 q8 q8
    q2 q8 q8 q3 q8 q8 q8
    *q3 q8 q8 q8 q4 q8 q8
    q4 q8 q8 q8 q8 q5 q8
    q5 q8 q8 q8 q6 q8 q8
    q6 q8 q8 q8 q8 q8 q7
    *q7 q8 q8 q8 q8 q8 q8
    q8 q8 q8 q8 q8 q8 q8
  3. Write a program to emulate the behavior of given DFA with the rules provided by (2)

SOURCE CODE:

public class DFAwithdeadend {
    public static void main(String[] args) {
        // Implement DFA that accepts 'int' or 'integer'
        int count;
        String state_now="q0",
               final_state1="q3",final_state2="q7";
        Scanner sc= new Scanner(System.in);
        System.out.print("Enter a string to test:");
        String string= sc.nextLine();
        HashMap i = new HashMap();
        HashMap n = new HashMap();
        HashMap t = new HashMap();
        HashMap e = new HashMap();
        HashMap g = new HashMap();
        HashMap r = new HashMap();
        HashMap deadend = new HashMap();
        i.put("q0","q1");
        n.put("q1","q2");
        t.put("q2","q3");
        e.put("q3","q4");
        g.put("q4","q5");
        e.put("q5","q6");
        r.put("q6","q7");
        for(count=0;count<=8;count++){
            String rem_state="q"+count;
            if (count!=0)
                i.put(rem_state,"q8");
            if (count!=1)
                n.put(rem_state,"q8");
            if (count!=2)
                t.put(rem_state,"q8");
            if (count!=3 && count!=5)
                e.put(rem_state,"q8");
            if (count!=4)
                g.put(rem_state,"q8");
            if (count!=6)
                r.put(rem_state,"q8");
            deadend.put(rem_state, "q8");
        }
        System.out.print("Tracing DFA..\nstart:q0");
        for(count=0;count<string.length();count++){
            if(string.charAt(count)=='i'){
              state_now=(String)i.get(state_now);
            }
            else if(string.charAt(count)=='n'){
                state_now=(String)n.get(state_now);
            }
            else if(string.charAt(count)=='t'){
                state_now=(String)t.get(state_now);
            }
            else if(string.charAt(count)=='e'){
                state_now=(String)e.get(state_now);
            }
            else if(string.charAt(count)=='g'){
                state_now=(String)g.get(state_now);
            }
            else if(string.charAt(count)=='r'){
                state_now=(String)r.get(state_now);
            }
            else{
                state_now=(String)deadend.get(state_now);
            }
            System.out.print("-->"+state_now); 
        }
        if(state_now.equals(final_state1)||state_now.equals(final_state2)){
            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!