C++의 입력(a, b)에서 'a'로 시작하고 끝나는 DFA를 빌드하는 프로그램

문자 'a'로 시작하고 끝나야 하는 문자 'a'와 'b'의 DFA 문자열이 주어지면 작업은 DFA를 통해 문자열이 'a'로 시작하고 끝나는지 여부를 찾는 것입니다.

DFA(Deterministic Finite Automata)란 무엇입니까?

이론적인 컴퓨터 과학의 한 분야인 계산 이론에서 Deterministic Finite Automata는 기호 문자열을 수락하거나 거부하는 유한 상태 기계입니다. 결정적은 실행할 계산의 고유성을 나타냅니다.

DFA로 문자열을 찾으려면 문자열은 입력(a, b)에서 'a'로 시작하고 끝나야 합니다. 메모리 개념이 없고 현재 문자만 저장할 수 있기 때문에 DFA는 제공된 문자열을 저장할 수 없습니다. 그렇지 않으면 제공된 시퀀스/문자열의 첫 번째 문자와 마지막 문자를 쉽게 확인할 수 있습니다.

예

Input: a b b a
Output: yes
Explanation: The input string starts and ends with ‘a’

Input: a a a b a b
Output: no

위의 문제를 해결하기 위해 우리가 따르고 있는 접근 방식 -

따라서 위에서 언급한 문제에 대해 DFA를 만든 다음 생성한 DFA에 따라 문제를 해결합니다.

dfa.jpg

알고리즘

Start
Step 1-> In main()
   Call function srand(time(0)) to generate random numbers
   Declare variable as int max = 1 + rand() % 15
   Declare and set int i = 0
   While(i < max)
      Declare char data = 'a' + rand() % 2
      Print data
      Increment i
      IF data = 'a'
         IF(i = max)
            Print "YES"
         End
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
            If (data = 'a' AND i = max)
               Print YES\n
            End
            Else IF(i = max)
               Print NO
            End
         End
      End
      Else
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
         End
         Print NO
      End
   End
Stop

예

#include <iostream>
#include <time.h>
using namespace std;
int main() {
   // for generating random numbers
   srand(time(0));
   int max = 1 + rand() % 15;
   int i = 0;
   while (i < max) {
      char data = 'a' + rand() % 2;
      cout << data << " ";
      i++;
      if (data == 'a') {
         if (i == max)
            cout << "YES\n";
         while (i < max) {
            data = 'a' + rand() % 2;
            cout << data << " ";
            i++;
            if (data == 'a' && i == max) {
               cout << "\nYES\n";
            } else if (i == max) {
               cout << "\nNO\n";
            }
         }
      } else {
         while (i < max) {
            data = 'a' + rand() % 2;
            cout << data << " ";
            i++;
         }
         cout << "\nNO\n";
      }
   }
   return 0;
}

출력

b b a b a b a b b b b b
NO