Deterministic Finite Automata (DFA)

DFAIn the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA), is a finite-state machine that accepts and rejects strings of symbols and only produces a unique computation (or run) of the automaton for each input string.*


*ReferenceWikipedia


Sample Code:

Q: Program for a DFA starting with aa over the alphabet {a,b}.

Solution:


#include<stdio.h>
#include<string.h>
void main()
{
    int i,j,n;
    char input[10];
    printf("\n\tProgram for the language starting with aa");

    printf("\nEnter the string: ");
    scanf("%s",input);

    n=strlen(input);

    if(input[0]=='a' && input[1]=='a')
    {
        j=1;    
        for(i=2;i<n;i++)
        {
            if(input[i]=='a' || input[i]=='b')
                j=1;
            else
            {
                printf("\nString Rejected\n");
                j=0;
                break;
            }
        }
    }
    else
        printf("\nString Rejected\n");

    if(j==1)
        printf("\nString Accepted\n");
}



OUTPUT::

1:
  Program for the language starting with aa
Enter the string: aabbaa

String Accepted

2:
Program for the language starting with aa
Enter the string: abab

String Rejected

3:
Program for the language starting with aa
Enter the string: cabd

String Rejected

4:
Program for the language starting with aa
Enter the string: aaaab

String Accepted

5:
Program for the language starting with aa
Enter the string: zxcdsa

String Rejected

Previous Post Next Post