The Automata Theory

The theoretical computer science is the study of formal languages. The theory of formal languages considered formalalized grammars and its created formal languages.

The automata theory is a part of theoretical computer science and a useful tool to solve the problem whether a word appertains to a formal language over an alphabet.

Given automaton:

  • alphabet: Σ = { a, b, c }
  • condition set: S = { s0, s1, s2, s3, s4 }
  • end condition set: F = { s1, s2, s3 }

    • Condition graph of automatonautomaton image
    list.h
    1#ifndef list_h
    2#define list_h
    3
    4struct List {
    5    char node;
    6    struct List *next;
    7};
    8
    9//prototypes
    10struct List *newnode(char);
    11void insert(struct List **, char);
    12void erase_head(struct List **);
    13void erase_list(struct List **);
    14void reverse(struct List **);
    15void print(struct List **);
    16
    17#endif
    list.cpp
    1#include <cstdlib>
    2#include <iostream>
    3#include "list.h"
    4
    5struct List *newnode(char node) {
    6    struct List *newelement = new struct List;
    7    newelement->node = node;
    8    newelement->next = NULL;
    9    return newelement;
    10}
    11
    12void insert(struct List **head, char node) {
    13    struct List *curr = newnode(node);
    14    curr->next = *head;
    15    (*head) = curr;
    16}
    17
    18void erase_head(struct List **head) {
    19    struct List *temp = *head;
    20    (*head) = temp->next;
    21    temp->next = NULL;
    22    temp = NULL;
    23    delete temp;
    24}
    25
    26void erase_list(struct List **head) {
    27    struct List *curr = *head;
    28    while(curr) {
    29        struct List *temp = curr;
    30        curr = curr->next;
    31        temp = NULL;
    32        delete temp;
    33    }
    34    (*head) = curr;
    35}
    36
    37void reverse(struct List **head) {
    38    struct List *prev = NULL;
    39    struct List *curr = *head;
    40    struct List *next;
    41    while(curr != NULL) {
    42        next = curr->next;
    43        curr->next = prev;
    44        prev = curr;
    45        curr = next;
    46    }
    47    (*head) = prev;
    48}
    49
    50void print(struct List **head) {
    51    struct List *curr = *head;
    52    while(curr) {
    53        std::cout << curr->node;
    54        curr = curr->next;
    55    }
    56}
    main.cpp
    1/*
    2    How to compile:
    3    g++ -o automaton list.cpp main.cpp
    4    
    5    Automaton with given
    6    alphabet Σ = {a,b,c},
    7    condititions S = {s0, s1, s2, s3, s4},
    8    start condition is s0 and
    9    end conditions are F = {s1, s2, s3}
    10    
    11    To example:
    12    - an accepted word is L1 = aabbbcc
    13    - a not accepted word is L2 = abba
    14*/
    15
    16#include <iostream>
    17#include "list.h"
    18
    19//prototypes
    20void create_list(struct List **, std::string);
    21int start(struct List **);
    22int s0(struct List **);
    23int s1(struct List **);
    24int s2(struct List **);
    25int s3(struct List **);
    26int s4(struct List **);
    27
    28int main() {
    29    struct List *list = NULL;
    30    std::string str;
    31    
    32    std::cout << "Automaton" << std::endl << "Alphabet: Σ = {a, b, c}" << std::endl;
    33    std::cout << "Input > ";
    34    std::cin >> str;
    35    
    36    create_list(&list, str);
    37    std::cout << "Given word in list:" << std::endl;
    38    print(&list);
    39    std::cout << std::endl;
    40    
    41    int word = start(&list);
    42    if(word == 0) std::cout << "Given word is not accepted" << std::endl;
    43    else std::cout << "Given word is accepted" << std::endl;
    44    
    45    delete list;
    46    
    47    return 0;
    48}
    49
    50void create_list(struct List **head, std::string str) {
    51    struct List *curr = *head;
    52    for(std::string::iterator i = str.begin(); i != str.end(); i++) insert(&curr, *i);
    53    reverse(&curr);
    54    (*head) = curr;
    55}
    56
    57int start(struct List **head) {
    58    int word = s0(head);
    59    erase_list(head);
    60    if(word == 1) return 1;
    61    return 0;
    62}
    63
    64int s0(struct List **head) {
    65    struct List *curr = *head;
    66    if(curr->node == 'a') {
    67        erase_head(&curr);
    68        return s1(&curr);
    69    }
    70    else if(curr->node == 'b') {
    71        erase_head(&curr);
    72        return s2(&curr);
    73    }
    74    else if(curr->node == 'c') {
    75        erase_head(&curr);
    76        return s4(&curr);
    77    }
    78    return 0;
    79}
    80
    81int s1(struct List **head) {
    82    struct List *curr = *head;
    83    if(curr == NULL) return 1;
    84    if(curr->node == 'a') {
    85        erase_head(&curr);
    86        return s1(&curr);
    87    }
    88    else if(curr->node == 'b') {
    89        erase_head(&curr);
    90        return s2(&curr);
    91    }
    92    else if(curr->node == 'c') {
    93        erase_head(&curr);
    94        return s3(&curr);
    95    }
    96    return 0;
    97}
    98
    99int s2(struct List **head) {
    100    struct List *curr = *head;
    101    if(curr == NULL) return 1;
    102    if(curr->node == 'a') {
    103        erase_head(&curr);
    104        return s4(&curr);
    105    }
    106    else if(curr->node == 'b') {
    107        erase_head(&curr);
    108        return s2(&curr);
    109    }
    110    else if(curr->node == 'c') {
    111        erase_head(&curr);
    112        return s3(&curr);
    113    }
    114    return 0;
    115}
    116
    117int s3(struct List **head) {
    118    struct List *curr = *head;
    119    if(curr == NULL) return 1;
    120    if(curr->node == 'a') {
    121        erase_head(&curr);
    122        return s4(&curr);
    123    }
    124    else if(curr->node == 'b') {
    125        erase_head(&curr);
    126        return s4(&curr);
    127    }
    128    else if(curr->node == 'c') {
    129        erase_head(&curr);
    130        return s3(&curr);
    131    }
    132    return 0;
    133}
    134
    135int s4(struct List **head) {
    136    struct List *curr = *head;
    137    if(curr == NULL) return 0;
    138    if(curr->node == 'a') {
    139        erase_head(&curr);
    140        return s4(&curr);
    141    }
    142    else if(curr->node == 'b') {
    143        erase_head(&curr);
    144        return s4(&curr);
    145    }
    146    else if(curr->node == 'c') {
    147        erase_head(&curr);
    148        return s4(&curr);
    149    }
    150    return 0;
    151}