DFA 接受包含“aba”作为子字符串的所有字符串 w ∈(a,b)* 的 C 程序

问题

设计一个用于语言 L={w1abaw2 | w1,w2 Є(a,b)*} 的 DFA，这意味着 DFA 接受所有包含“aba”作为子字符串的字符串。

解决方案

语言 L= {aba,aabaa, aabab, babab, ababa, …….} 接受的字符串。

步骤 1 - 最小字符串（起始字符串）的转换图 -

如果 w1 和 w2 为空，则生成的字符串为“aba”，因为 w1、w2 ε(a,b)*

q0 是初始状态，q3 是最终状态。

步骤 2 - 给定语言的最终 DFA 如下所示 -

解释

  • qo 是初始状态，q0 在 'a' 上转到 q1，在 'b' 上转到 q0，根据 DFA，每个状态都必须对两个输入生成一个转换。

  • q1 在 'a' 上转到 q1，在 'b' 上转到 q2，我们必须牢记根据给定的语言，我们需要生成一个子字符串“aba”。

  • q2 在 'a' 上转到 q3，在 'b' 上转到 q0 状态。

  • q3 是最终状态，在输入 'a' 和 'b' 上都只转到 q3。

转换表

让我们看看如下所示的转换表 -

当前状态输入 a输入 b
q0q1q0
q1q1q2
q2q3q0
*q3q3q3

示例

以下是构建 DFA 的 C 程序，该 DFA 接受所有包含“aba”作为子字符串的字符串 w ε(a,b)* -

 在线演示

#include <stdio.h>
#include <string.h>
void checkDFA(char s[] ) {
   // storing initial state
   int initialState = 0;
   //assign initial state to previous state.
   int previousState = initialState;
   int finalState;
   for(int i = 0; i < strlen(s); i++)    {
      if((previousState == 0 && s[i] == 'a') || (previousState == 1 && s[i] == 'a')) {
         finalState = 1;
      }
      if((previousState == 0 && s[i] == 'b') || (previousState == 2 && s[i] == 'b')) {
         finalState = 0;
      }
      if(previousState == 1 && s[i] == 'b') {
         finalState = 2;
      }
      if((previousState == 2 && s[i] == 'a') || (previousState == 3)) {
         finalState = 3;
      }
      previousState = finalState;
   }
   if(finalState == 3) {
      printf("given string is Accepted");
   }
   else
   {
      printf("given string is Not Accepted");
   }
}
int main() {
   // Given string
   char s[40];
   printf("implementation of DFA which having a sub string 'aba':
 enter a string:");
   scanf("%s",s);
   checkDFA(s);
   return 0;
}

输出

输出如下所示 -

Run 1:
implementation of DFA which having a sub string 'aba':
enter a string:aba
given string is Accepted.
Run 2:
implementation of DFA which having a sub string 'aba':
enter a string:abba
given string is Not Accepted.

更新于: 2021-06-14

2K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告