Создайте 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 
            

                    
                                            Статьи
                                            Алгоритмы
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКак повысить эффективность вашего сайта: комплексный подход
28 Июня, 2025
Как создать интерактивный сайт без навыков программирования
23 Июня, 2025
Как создать интерактивный сайт без навыков программирования
23 Июня, 2025
Как создать эффективный сайт: от идеи до запуска
19 Июня, 2025
Гибридные СХД — баланс скорости и объема для современного бизнеса
21 Мая, 2025
Мобильная разработка в 2025 году: как выбрать между нативным и кроссплатформенным подходом
21 Мая, 2025
Как виртуальные номера меняют бизнес-коммуникации IT-компаний
17 Мая, 2025
Революция в SEO: Как инструменты массового открытия URL меняют правила игры
10 Мая, 2025


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2025. Все права защищены.