Создайте DFA, чтобы принимать двоичные строки, которые начинаются или заканчиваются на «01»

Опубликовано: 5 Января, 2022

Для данной двоичной строки str задача состоит в том, чтобы построить DFA, который принимает строку, если строка либо начинается с «01», либо заканчивается на «01».

Input: str = “010000” 
Output: Accepted 
Explanation: 
The given string starts with “01”.

Input: str = “1100111” 
Output: Not Accepted 
Explanation: 
The given string neither starts with nor ends with “01”. 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

DFA или детерминированные конечные автоматы - это конечный автомат, который принимает строку (при определенных условиях), если она достигает конечного состояния, в противном случае отклоняет ее.
В DFA нет понятия памяти, поэтому мы должны проверять строку посимвольно, начиная с 0-го символа. Вводимый набор символов для задачи: {0, 1}. Чтобы DFA был действительным, должно быть определено правило перехода для каждого символа входного набора в каждом состоянии в допустимое состояние. Поэтому для разработки DFA выполняются следующие шаги:

  • В этом случае допустимы строки, которые начинаются с 01 или заканчиваются на 01, либо оба начинаются с 01 и заканчиваются 01.
  • Сделайте начальное состояние и переведите его входные алфавиты, то есть 0 и 1, в два разных состояния.
  • Проверяйте соответствие строки после каждого перехода, чтобы игнорировать ошибки.
  • Сначала сделайте DfA для строки минимальной длины, затем продолжайте шаг за шагом.
  • Определите конечное состояние (я) в соответствии с приемлемостью строки.

Пошаговый подход к разработке DFA:

  • Шаг 1: Сделайте начальное состояние «А». Минимально возможная строка - 01, что приемлемо. Для этого выполните переход 0 из состояния «A» в состояние «B», а затем выполните переход 1 из состояния «B» в состояние «C» и обратите внимание на это состояние «C» как конечное состояние.

  • Шаг 2. Теперь мы разработали DFA, который начинается с 01. Чтобы принять все строки, начинающиеся с 01, такие как 011, 010, 010000, 01111, 010101000010001 и т. Д., Нам нужно поместить в состояние «С». Этот цикл содержит все комбинации 0 и 1.

  • Шаг 3: Теперь нам нужно подумать о строке, которая заканчивается на «01». Мы осуществили переход 0 состояния «A», затем вход 1 состояния «A». При этой минимально возможной строке, которая заканчивается на 01, будет 101. Для этого выполните переход входа 1 из состояния «A» в состояние «D», затем выполните переход входа 0 из состояния «D» в состояние «E» и затем выполните переход входа 1 из состояния «E» в состояние «F» и отметьте это состояние «F» как конечное состояние.

  • Шаг 4: Есть еще одна возможность, что любое количество единиц идет в начале, а затем заканчивается на 01. Для этого сделайте самостоятельный цикл из 1 в состоянии «D», и любое количество нулей может стоять перед 1, которое появляется в конец. Для этого установите самопетлю в 0 и состояние «E».

  • Шаг 5: До сих пор мы закончили со строками, которые начинаются с 1 и заканчиваются 01. Теперь нам нужно подумать о строке, которая начинается с 0 и заканчивается на 01. Для этого выполните переход входа 0 из состояния « B », чтобы указать« E ».

  • Шаг 6: Теперь у нас остались только входные алфавиты состояния «F». Переведите вход 1 из состояния «F» в состояние «D», а затем выполните переход входа 0 из состояния «F» в состояние «E».

Таблица переходов и правила перехода вышеуказанного DFA:

Состояние Вход (0) Вход (1)
-> А B D
B E C
C * C C
D E D
E E F
F * E D

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program to check if a string
// either starts or ends with 01
#include<bits/stdc++.h>
using namespace std;
void stateA(string);
void stateB(string);
void stateC(string);
void stateD(string);
void stateE(string);
void stateF(string);
// Function for transition
// state A
void checkstateA(string n)
{
// State transition to
// B if the character is
// 0
if (n[0] == '0' )
stateB(n.substr(1));
// State transition to
// D if the character is
// 1
else
stateD(n.substr(1));
}
// Function for transition
// state B
void stateB(string n)
{
// Check if the string has
// ended
if (n.length() == 0)
cout << "string not accepted" ;
else
{
// State transition to C
// if the character is 1
if (n[0] == '1' )
stateC(n.substr(1));
// State transition to D
// if the character is 0
else
stateD(n.substr(1));
}
}
// Function for transition
// state C
void stateC(string n)
{
cout << "String accepted" ;
}
// Function for transition
// state D
void stateD(string n)
{
if (n.length() == 0)
cout << "string not accepted" ;
else
{
// State transition to D
// if the character is 1
if (n[0] == '1' )
stateD(n.substr(1));
// State transition to E
// if the character is 0
else
stateE(n.substr(1));
}
}
// Function for transition
// state E
void stateE(string n)
{
if (n.length() == 0)
cout << "string not accepted" ;
else
{
// State transition to E
// if the character is 0
if (n[0] == '0' )
stateE(n.substr(1));
// State transition to F
// if the character is 1
else
stateF(n.substr(1));
}
}
// Function for transition
// state F
void stateF(string n)
{
if (n.length() == 0)
cout << "string accepred" ;
else
{
// State transition to D
// if the character is 1
if (n[0] == '1' )
stateD(n.substr(1));
// State transition to E
// if the character is 0
else
stateE(n.substr(1));
}
}
// Driver code
int main()
{
string n = "0100101" ;
checkstateA(n);
return 0;
}
// This code is contributed by chitranayal

Джава

// Java program to check if a string
// either starts or ends with 01
import java.util.*;
class GFG{
// Function for transition
// state A
static void checkstateA(String n)
{
// State transition to
// B if the character is
// 0
if (n.charAt( 0 ) == '0' )
stateB(n.substring( 1 ));
// State transition to
// D if the character is
// 1
else
stateD(n.substring( 1 ));
}
// Function for transition
// state B
static void stateB(String n)
{
// Check if the string has
// ended
if (n.length() == 0 )
System.out.println( "string not accepted" );
else
{
// State transition to C
// if the character is 1
if (n.charAt( 0 ) == '1' )
stateC(n.substring( 1 ));
// State transition to D
// if the character is 0
else
stateD(n.substring( 1 ));
}
}
// Function for transition
// state C
static void stateC(String n)
{
System.out.println( "String accepted" );
}
// Function for transition
// state D
static void stateD(String n)
{
if (n.length() == 0 )
System.out.println( "string not accepted" );
else
{
// State transition to D
// if the character is 1
if (n.charAt( 0 ) == '1' )
stateD(n.substring( 1 ));
// State transition to E
// if the character is 0
else
stateE(n.substring( 1 ));
}
}
// Function for transition
// state E
static void stateE(String n)
{
if (n.length() == 0 )
System.out.println( "string not accepted" );
else
{
// State transition to E
// if the character is 0
if (n.charAt( 0 ) == '0' )
stateE(n.substring( 1 ));
// State transition to F
// if the character is 1
else
stateF(n.substring( 1 ));
}
}
// Function for transition
// state F
static void stateF(String n)
{
if (n.length() == 0 )
System.out.println( "string accepred" );
else
{
// State transition to D
// if the character is 1
if (n.charAt( 0 ) == '1' )
stateD(n.substring( 1 ));
// State transition to E
// if the character is 0
else
stateE(n.substring( 1 ));
}
}
// Driver Code
public static void main(String args[])
{
String n = "0100101" ;
checkstateA(n);
}
}
// This code is contributed by jyoti369

Python3

# Python3 program to check if
# a string either starts or
# ends with 01
# Function for transition
# state A
def checkstateA(n):
# State transition to
# B if the character is
# 0
if (n[ 0 ] = = '0' ):
stateB(n[ 1 :])
# State transition to
# D if the character is
# 1
else :
stateD(n[ 1 :])
# Function for transition
# state B
def stateB(n):
# Check if the string has
# ended
if ( len (n) = = 0 ):
print ( "string not accepted" )
else :
# State transition to C
# if the character is 1
if (n[ 0 ] = = '1' ):
stateC(n[ 1 :])
# State transition to D
# if the character is 0
else :
stateD(n[ 1 :])
# Function for transition
# state C
def stateC(n):
print ( "String accepted" )
# Function for transition
# state D
def stateD(n):
if ( len (n) = = 0 ):
print ( "string not accepted" )
else :
# State transition to D
# if the character is 1
if (n[ 0 ] = = '1' ):
stateD(n[ 1 :])
# State transition to E
# if the character is 0
else :
stateE(n[ 1 :])
# Function for transition
# state E
def stateE(n):
if ( len (n) = = 0 ):
print ( "string not accepted" )
else :
# State transition to E
# if the character is 0
if (n[ 0 ] = = '0' ):
stateE(n[ 1 :])
# State transition to F
# if the character is 1
else :
stateF(n[ 1 :])
# Function for transition
# state F
def stateF(n):
if ( len (n) = = 0 ):
print ( "string accepred" )
else :
# State transition to D
# if the character is 1
if (n[ 0 ] = = '1' ):
stateD(n[ 1 :])
# State transition to E
# if the character is 0
else :
stateE(n[ 1 :])
# Driver code
if __name__ = = "__main__" :
n = "0100101"
checkstateA(n)

C #

// C# program to check if
// a string either starts
// or ends with 01
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function for transition
// state A
static void checkstateA( string n)
{
// State transition to
// B if the character is
// 0
if (n[0] == '0' )
stateB(n.Substring(1));
// State transition to
// D if the character is
// 1
else
stateD(n.Substring(1));
}
// Function for transition
// state B
static void stateB( string n)
{
// Check if the string has
// ended
if (n.Length == 0)
{
Console.Write( "string not accepted" );
}
else
{
// State transition to C
// if the character is 1
if (n[0] == '1' )
stateC(n.Substring(1));
// State transition to D
// if the character is 0
else
stateD(n.Substring(1));
}
}
// Function for transition
// state C
static void stateC( string n)
{
Console.Write( "string accepted" );
}
// Function for transition
// state D
static void stateD( string n)
{
if (n.Length == 0)
Console.Write( "string not accepted" );
else
{
// State transition to D
// if the character is 1
if (n[0] == '1' )
stateD(n.Substring(1));
// State transition to E
// if the character is 0
else
stateE(n.Substring(1));
}
}
// Function for transition
// state E
static void stateE( string n)
{
if (n.Length == 0)
Console.Write( "string not accepted" );
else
{
// State transition to E
// if the