Создайте DFA, чтобы принимать двоичные строки, которые начинаются или заканчиваются на «01»
Для данной двоичной строки 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”.
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
РЕКОМЕНДУЕМЫЕ СТАТЬИ |