Non-Deterministic Finite Automata (NFA)

NFA: In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if

• each of its transitions is uniquely determined by its source state and input symbol, and
• reading an input symbol is required for each state transition.

A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions.*

*Reference: Wikipedia

Sample Code:

Q: Program for NFA ending with 11 over the alphabet {0,1}.

Solution:

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

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

    n=strlen(input);

    if(input[n-1]=='1' && input[n-2]=='1')
    {
        j=1;
        for(i=0;i<n-2;i++)
        {
            if(input[i]=='0' || input[i]=='1')
                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 ending with 11
Enter String::10111

String Accepted

2:

 Program for the language ending with 11
Enter String::11

String Accepted

3:

 Program for the language ending with 11
Enter String::1010101011    

String Accepted

4:

 Program for the language ending with 11
Enter String::210011

String Rejected

5:

 Program for the language ending with 11
Enter String::10101

String Rejected