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

comments 0 Blogger Comments

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.

Read More

DFA to accept string with even a and even b

comments 0 Blogger Comments

Procedure:
1. Make a state diagram for DFA having even a and even b

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.

public class DfaEvenAB {
    public static void main(String[] args) {
        //Implementing DFA with even a and b
        String state="q0";
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the String:");
       String exp=sc.nextLine();
       HashMap a = new HashMap();
       HashMap b = new HashMap();
       a.put("q0","q1");
       a.put("q1","q0");
       a.put("q2","q3");
       a.put("q3","q2");
       b.put("q0","q3");
       b.put("q1","q2");
       b.put("q2","q1");
       b.put("q3","q0");
       
        System.out.print("Tracing DFA:\nstart=q0");
        for(int i=0;i<exp.length();i++){
            String str=""+exp.charAt(i);
            if(str.equals("a")){
                state=(String)a.get(state);
            }else if(str.equals("b")){
                state=(String)b.get(state);
            }
            System.out.print("-->"+state);
        }
        if(state.equals("q0")){
            System.out.println("\nString Accepted");
        }else{
            System.out.println("\nString not Accepted. Try another String.");
        }
    }
}

Output:

When String is Accepted:

When String is not accepted:

Read More

Implement DFA ending with 'abb'

comments 0 Blogger Comments

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.

Read More