Automata Theory codes.

checkRegularGrammer.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
typedef struct Translation Translation;
typedef struct State State;

typedef struct Translation
{
    struct State *nextState;
    char input;
}Translation;

typedef struct State
{
    /* data */
    bool isFinal;
    Translation *translations;
}State;

int main(int argc, char const *argv[])
{
    /* This is the code for Regular Grammer a*b* */
    // Taking input
    char str[1000];
    printf("Give an input string\n");
    scanf("%s", str);
    int m = strlen(str);
    // Defining States
    State q0 = {.isFinal=true};
    State q1 = {.isFinal=true};
    State q2 = {.isFinal=false};
    int transactionLen = 2;
    q0.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q0.translations[0].input='a';
    q0.translations[0].nextState = &q0;
    q0.translations[1].input='b'; 
    q0.translations[1].nextState = &q1;
    q1.translations = (Translation*)malloc(sizeof(Translation) * transactionLen);
    q1.translations[0].input='a';
    q1.translations[0].nextState = &q2;
    q1.translations[1].input='b'; 
    q1.translations[1].nextState = &q1;
    q2.translations = (Translation*)malloc(sizeof(Translation) * transactionLen);
    q2.translations[0].input='a';
    q2.translations[0].nextState = &q2;
    q2.translations[1].input='b'; 
    q2.translations[1].nextState = &q2;
    
    State currentState = q0;
    bool is_found = false;
    for(int i = 0; i < m; i++)
    {
        char currentInp = str[i];
        is_found = false;
        for(int j=0; j < transactionLen; j++){
            if(currentState.translations[j].input == currentInp){
                currentState = *currentState.translations[j].nextState;
                is_found = true;
                break;
            }
        }
        if(is_found == false){
            break;
        }
        
    }
    if(is_found ==  false){
        printf("Halting! Wrong input format\n");
    }
    else{
        if(currentState.isFinal == true){
            printf("String accepted\n");
        }
        else{
            printf("String Rejected\n");
        }
    }

    return 0;
}

grammer2lang.py

def main():
    n = int(input('Write number of rules\n'))
    rules = [None] * n
    for i in range(n):
        rules[i] = input()
    variables = {}
    for rule in rules:
        if rule[0] in variables:
            variables[rule[0]].append(rule.split(':')[-1].split('|'))
        else:
            variables[rule[0]] = rule.split(':')[-1].split('|')
    states = variables[rules[0][0]]
    i = 0
    while i < 100:
        i += 1
        num_states = len(states)
        new_states = []
        to_be_removed = []
        for i in range(num_states):
            for ch in states[i]:
                if ch in variables.keys():
                    to_be_removed.append(states[i])
                    var = variables[ch]
                    for v in var:
                        new_states.append(states[i].replace(ch, v))
        to_be_removed = list(set(to_be_removed))
        if len(to_be_removed) == 0:
            break
        states = states + new_states
        states = list(set(states))
    print('Outputs are')
    to_be_printed = []
    for i in range(len(states)):
        # replacing ~ with ''
        if states[i].find('~') != -1:
            states[i] = states[i].replace('~', '')
        # Removing Variables
        print_it = True
        for ch in states[i]:
            if ch in variables:
                print_it = False
                break
        if print_it:
            to_be_printed.append(states[i])
    print(sorted(to_be_printed))
                    
        
if __name__ == '__main__':
    main()

input.txt

aaaabbbbbbbbbbbbbb

regtest.txt

2
S:aAAA
A:bA|~

regWithFile.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct Translation Translation;
typedef struct State State;

typedef struct Translation
{
    struct State *nextState;
    char input;
}Translation;

typedef struct State
{
    /* data */
    bool isFinal;
    Translation *translations;
}State;

int main(int argc, char const *argv[])
{
    /* This is the code for a*b* */
    // Taking input from the file
    char ch;
    FILE *fp;
    char fileName[100] = "input.txt";
    fp = fopen(fileName, "r");
    // Defining States
    State q0 = {.isFinal=true};
    State q1 = {.isFinal=true};
    State q2 = {.isFinal=false};
    int transactionLen = 2;
    q0.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q0.translations[0].input='a';
    q0.translations[0].nextState = &q0;
    q0.translations[1].input='b'; 
    q0.translations[1].nextState = &q1;
    q1.translations = (Translation*)malloc(sizeof(Translation) * transactionLen);
    q1.translations[0].input='a';
    q1.translations[0].nextState = &q2;
    q1.translations[1].input='b'; 
    q1.translations[1].nextState = &q1;
    q2.translations = (Translation*)malloc(sizeof(Translation) * transactionLen);
    q2.translations[0].input='a';
    q2.translations[0].nextState = &q2;
    q2.translations[1].input='b'; 
    q2.translations[1].nextState = &q2;
    
    State currentState = q0;
    bool is_found = false;
    while((ch = fgetc(fp)) != EOF)
    {
        char currentInp = ch;
        is_found = false;
        for(int j=0; j < transactionLen; j++){
            if(currentState.translations[j].input == currentInp){
                currentState = *currentState.translations[j].nextState;
                is_found = true;
                break;
            }
        }
        if(is_found == false){
            break;
        }
        
    }
    if(is_found ==  false){
        printf("Halting! Wrong input format\n");
    }
    else{
        if(currentState.isFinal == true){
            printf("String accepted\n");
        }
        else{
            printf("String Rejected\n");
        }
    }

    return 0;
}

turing1.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct Translation Translation;
typedef struct State State;

typedef struct Translation
{
    struct State *nextState;
    char input;
    char replaceWith;
    char direction;
}Translation;

typedef struct State
{
    /* data */
    bool isFinal;
    Translation *translations;
}State;

int main(int argc, char const *argv[])
{
    /* Turing machine to calculate f mod 5 */
    /* Input has be in unary(i.e "1111") format */
    /* Output will be returned in unary format */
    // Taking input
    char str[1000];
    printf("Give an input string\n");
    scanf("%s", str);
    int m = strlen(str);
    // Defining States
    State q0 = {.isFinal=false};
    State q1 = {.isFinal=false};
    State q2 = {.isFinal=false};
    State q3 = {.isFinal=false};
    State q4 = {.isFinal=false};
    State q5 = {.isFinal=true};

    int transactionLen = 2;
    q0.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q0.translations[0].input='1';
    q0.translations[0].nextState = &q1;
    q0.translations[0].direction = 'r';
    q0.translations[0].replaceWith = '_';
    q0.translations[1].input='_'; 
    q0.translations[1].nextState = &q5;
    q0.translations[1].direction = 'r';
    q0.translations[1].replaceWith = '_';
    q1.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q1.translations[0].input='1';
    q1.translations[0].nextState = &q2;
    q1.translations[0].direction = 'r';
    q1.translations[0].replaceWith = '_';
    q1.translations[1].input='_'; 
    q1.translations[1].nextState = &q0;
    q1.translations[1].direction = 'l';
    q1.translations[1].replaceWith = '1';
    q2.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q2.translations[0].input='1';
    q2.translations[0].nextState = &q3;
    q2.translations[0].direction = 'r';
    q2.translations[0].replaceWith = '_';
    q2.translations[1].input='_'; 
    q2.translations[1].nextState = &q1;
    q2.translations[1].direction = 'l';
    q2.translations[1].replaceWith = '1';
    q3.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q3.translations[0].input='1';
    q3.translations[0].nextState = &q4;
    q3.translations[0].direction = 'r';
    q3.translations[0].replaceWith = '_';
    q3.translations[1].input='_'; 
    q3.translations[1].nextState = &q2;
    q3.translations[1].direction = 'l';
    q3.translations[1].replaceWith = '1';
    q4.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q4.translations[0].input='1';
    q4.translations[0].nextState = &q0;
    q4.translations[0].direction = 'r';
    q4.translations[0].replaceWith = '_';
    q4.translations[1].input='_'; 
    q4.translations[1].nextState = &q4;
    q4.translations[1].direction = 'l';
    q4.translations[1].replaceWith = '1';
    q5.translations = (Translation*) malloc(sizeof(Translation) * transactionLen);
    q5.translations[0].input='1';
    q5.translations[0].nextState = &q5;
    q5.translations[0].direction = 'r';
    q5.translations[0].replaceWith = '1';
    q5.translations[1].input='_'; 
    q5.translations[1].nextState = &q5;
    q5.translations[1].direction = 'l';
    q5.translations[1].replaceWith = '_';
    State currentState = q0;
    bool is_found = false;
    int i = 0;
    while(currentState.isFinal != true)
    {
        is_found = false;
        if(str[i] == '\0'){
            str[i] = '_';
            str[i+1] = '\0';
        }
        char currentInp = str[i];
        for(int j=0; j < transactionLen; j++){
            if(currentState.translations[j].input == currentInp){
                str[i] = currentState.translations[j].replaceWith;
                if(currentState.translations[j].direction == 'l'){
                    i = (i - 1) % 1000;
                }
                else{
                    i = (i + 1) % 1000;
                }
                currentState = *currentState.translations[j].nextState;
                is_found = true;
                break;
            }
        }
        if(is_found == false){
            break;
        }
        
    }
    if(is_found ==  false){
        printf("Halting! Wrong input format\n");
    }
    else{
        if(currentState.isFinal == true){
            m = strlen(str);
            printf("Hence the mod value is ");
            for(int i =0; i < m; i++){
                if(str[i] !='_'){
                    printf("%c", str[i]);
                }
            }
            printf("\n");
        }
    }

    return 0;
}