Рубрики

C-программа для моделирования недетерминированных конечных автоматов (NFA)

Фон

NFA обычно описывается с использованием ориентированного графа. Каждое ребро и вершина помечены 0 или 1, представляя возможные переходы. Вершины представляют состояния NFA. Обозначенные 0 являются неприемлемыми состояниями, а помеченные 1 — принимающими состояниями.

  • Требуется входная строка конечной длины. Обычно входная строка представляет собой двоичную последовательность из 0 и 1.
  • Мы начинаем с вершины 1, которая всегда является начальным состоянием, и следуем за ребрами, последовательно заданными битами входной строки, пока у входной строки не останется дополнительного бита.
  • Термин «недетерминированный» означает, что в любом состоянии V у нас есть несколько вариантов следования ребру. NFA использует входную строку, а набор состояний Q представляет возможные ходы NFA.
  • Если Q содержит хотя бы одно состояние, в котором принимается последняя вершина, мы говорим, что NFA принял входную строку, в противном случае NFA отклонил входную строку.

Пример NFA:

Starting state - vertex 1
Accepting states - Vertices with double circles(label 1) // Vertex 4
Non ­accepting states - single circles (label 0). // Vertices 1, 2 and 3.

Как проверить прием строки?

Для ввода: 1010

  • В состоянии 1 у нас есть две возможности: либо следовать циклу самообслуживания и оставаться в состоянии 1, либо следовать ребру, обозначенному 1, и перейти в состояние 3.
                            {1} 1010 --> {1, 3} 010
  • В состоянии 3 нет ребра с меткой 0, поэтому вычисления не будут выполняться.
  • В состоянии 1 у нас есть две возможности: либо следовать самому циклу и оставаться в состоянии 1, либо следовать ребру, обозначенному 0, до состояния 2.
                            {1, 3} 010 --> {1, 2} 10
  • Теперь нет никакого ребра, помеченного 1 из состояния 2. Вычисление исчезнет. У нас есть две возможности: либо следовать по самопроверке до состояния 1, либо следовать за ребром, обозначенным 1, до состояния 3.
                             {1, 2} 10 --> {1, 3} 0
  • В состоянии 3 нет ребра с меткой 0. Таким образом, вычисление прекратится. В состоянии 1 у нас есть две возможности: либо следовать по самому циклу, чтобы перейти в состояние 1, либо по ребру, обозначенному 0, до состояния 2.
                                 {1, 3} 0 --> {1, 2}
  • Теперь NFA потребляет ввод. Это может быть либо в состояниях 1 или 2, оба из которых не принимают. Таким образом, NFA отклонил ввод 1010.

Для ввода: 1100

          {1} 1100 --> {1, 3} 100 {1, 3} 100 --> {1, 3, 4} 00 {1, 3, 4} 
                  00--> {1, 2, 4} 0 {1, 2, 4} 0--> {1, 2, 4}
  • Теперь NFA потребляет ввод. Он может быть в состоянии 1, 2 или 4. Состояние 4 является принимающим состоянием. Итак, NFA принимает строку 1100.
  • Мы можем легко проверить, что данный NFA принимает все двоичные строки с «00» и / или «11» в качестве подстроки.

C Программа для моделирования недетерминированных конечных автоматов (NFA)

Формат ввода: представление списка смежности NFA в следующем формате.

Данный пример будет представлен как

Общее количество ребер: 4

Edge Connectivity:

1 0 4 0 1 0 2 1 1 1 3

2 0 1 0 4

3 0 1 1 4

4 1 2 0 4 1 4

Формат вывода: первые 10 двоичных строк, которые принимаются NFA в лексикографическом порядке (e обозначает пустую строку): {e, 0, 1, 00, 01, 10, 11, 000,…}

Пример вывода для данного контрольного примера следующий:

00

11

000

001

011

100

110

111

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

  

int row = 0;

  
// Структура для представления узла списка смежности

struct node

{

    int data;

    struct node* next;

    char edgetype;

  

}typedef node;

  
// Добавляем ребро в список смежности

node* push(node* first , char edgetype , int data)

{

    node* new_node = (node*)malloc(sizeof(node));

    new_node->edgetype = edgetype;

    new_node->data = data;

    new_node->next = NULL;

    if (first==NULL)

    {

        first = new_node;

        return new_node;

    }

    first->next = push(first->next,edgetype,data);

    return first;

}

  
// Рекурсивная функция для проверки приема ввода

int nfa(node** graph, int current, char* input,

        int* accept, int start)

{

    if (start==(int)strlen(input))

        return accept[current];

  

    node* temp = graph[current];

    while (temp != NULL)

    {

      if (input[start]==temp->edgetype)

        if (nfa(graph,temp->data,input,accept,start+1==1)

           return 1;

      temp=temp->next;

    }

    return 0;

}

  
// Функция для генерации двоичных строк размером n

void generate(char** arr, int size, char *a)

{

    if (size==0)

    {

        strcpy(arr[row], a);

        row++;

        return;

    }

    char b0[20] = {'\0'};

    char b1[20] = {'\0'};

    b0[0] = '0';

    b1[0] = '1';

  

    // Рекурсивно генерируем двоичную строку

    generate((char**)arr, size-1, strcat(b0,a)); // Добавить 0 впереди

    generate((char**)arr, size-1, strcat(b1,a)); // Добавить 1 перед

    return;

  
}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n;

    int i, j;

    scanf("%d", &n); // Количество узлов

    node* graph[n+1]; // Создать график

  

    for (i=0;i<n+1;i++)

        graph[i]=NULL;

  

  

    int accept[n+1]; // Массив для хранения состояния вершины

  

    for (i=0; i<n; i++)

    {

        // Индекс вершины, Состояние принятия, Количество ребер

        int index,acc,number_nodes;

        scanf("%d%d%d",&index,&acc,&number_nodes);

        accept[index]=acc; // Прием магазина

  

        for (j=0;j<number_nodes;j++) // Добавить все ребра

        {

            int node_add;

            int edge;

            scanf("%d%d",&edge,&node_add);

            graph[index] = push(graph[index],'0'+edge,node_add);

        }

    }

  

    int size = 1; // Размер ввода

    int count = 0; // Сохраняем количество выходных строк

  

    if (accept[1]==1) // Проверка на пустую строку

    {

        printf("e\n");

        count++;

    }

  

    while (count < 11)

    {

        char** arr;

        int power = pow(2,size);

        arr = (char**)malloc(power*sizeof(char*));

  

        for (i=0;i<power;i++)

            arr[i] = (char*)malloc(size*sizeof(char));

  

        char a[20] = {'\0'};

  

        generate((char**)arr,size,a); // Генерируем входы

  

        for (i=0; i<power; i++)

        {

            char input[20] = {'\0'};

  

            for (j=0; j<size; j++)

            {

                char foo[2];

                foo[0] = arr[i][size-1-j];

                foo[1] = '\0';

                strcat(input,foo);

                                // Копировать сгенерированный ввод строки

            }

  

            int result = nfa(graph,1,input,accept,0);

                        // Сохраняем результат nfa

  

            if (result==1)

            {

                printf("%s\n",input);

                                // Распечатать, если принято

                count++;

            }

  

            if (count==10)

                return 0;

        }

  

        size++; // Увеличиваем размер ввода двоичной строки

        row=0;

    }

  

    return 0;

}

Входные данные :

4
1 0 4 0 1 0 2 1 1 1 3
2 0 1 0 4
3 0 1 1 4
4 1 2 0 4 1 4

Выход:

00
11
000
001
011
100
110
111
0000
0001

Эта статья предоставлена Арджуном Мулраджани . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

C-программа для моделирования недетерминированных конечных автоматов (NFA)

0.00 (0%) 0 votes