Finite Automata se conoce como una máquina de estados finitos que son aceptables, de lo contrario no son aceptables. en el alfabeto de entrada ‘0’ y 1′.
- Determinar el estado inicial.
- La transición ocurre en cada alfabeto de entrada.
- Determine si el bucle automático debe aplicarse o no.
- El estado final de Mark.
Diseño de DFA paso a paso:
Paso 1:
haga que el estado inicial sea «A», entonces existe la posibilidad de que no haya ningún ‘0’ pero solo tenga ‘1’ en la string, lo cual es aceptable porque 0 es divisible por 3. Entonces , en este caso, ningún número de 1 puede estar presente aquí y para esto coloque el bucle automático de ‘1’ en el estado inicial «A».
Paso 2:
Cree la transición del alfabeto de entrada ‘0’ del estado «A» al estado «B».
Paso 3:
Después de un ‘0’, cualquier número de 1 puede estar presente, es decir, ningún ‘1’ o más de un ‘1’. Para esto, coloque el bucle de ‘1’ en el estado «B».
Paso 4:
Ahora cree la transición del alfabeto de entrada ‘0’ del estado «B» al estado «C» y después de dos 0 se puede encontrar cualquier número de 1 en la string y para esto coloque el bucle automático de ‘1’ en el estado inicial «C».
Paso 5:
antes de la transición del tercer ‘0’, debemos pensar en la lógica para que, después de esta transición, la máquina acepte una string que tenga un número de ceros divisible por 3. Para este tránsito ‘o’ del estado «C» al estado “A”. Como el tercer cero está llegando al estado “A”, entonces haga que el estado “A” sea el estado final.
Tabla de transición de DFA anterior:
estados | Entrada (0) | Entrada (1) |
---|---|---|
—> Un * | B | A |
B | C | B |
C | A | C |
En la tabla anterior, —> representa el estado inicial y * representa el estado final. En este artículo, el estado inicial y final es el mismo que es el estado final.
Reglas de transición de DFA anterior:
Implementar :
Java
// Java code for the above DFA import java.util.*; class GFG{ // Function for the state A static void checkStateA(String n) { // Check length of n // is 0 then print // String accepted if (n.length() == 0) System.out.print("String accepted"); // If 1 is found call function // checkStateA otherwise if 0 // is found call function stateB else { if (n.charAt(0) == '1') checkStateA(n.substring(1)); else stateB(n.substring(1)); } } // Function for the state B static void stateB(String n) { // Check length of n // is 0 then print // String not accepted if (n.length() == 0) System.out.print("String not accepted"); // If 1 is found call function // stateB otherwise if 0 // is found call function stateC else { if (n.charAt(0) == '1') stateB(n.substring(1)); else stateC(n.substring(1)); } } // Function for the state C static void stateC(String n) { // Check length of n // is 0 then print // String not accepted if (n.length() == 0) System.out.print("String not accepted"); // If 1 is found call function // stateC otherwise if 0 // is found call function checkStateA else { if (n.charAt(0) == '1') stateC(n.substring(1)); else checkStateA(n.substring(1)); } } // Driver code public static void main(String []args) { Scanner sc = new Scanner(System.in); // Take String input String n = sc.nextLine(); // Call checkStateA to // check the inputted String checkStateA(n); } } // This code is contributed by pratham76
Python3
# Python3 code for the above DFA def checkStateA(n): # check length of n # is 0 then print # string accepted if(len(n)== 0): print("string accepted") # if 1 is found call function # checkStateA otherwise if 0 # is found call function stateB else: if(n[0]=='1'): checkStateA(n[1:]) else: stateB(n[1:]) def stateB(n): # check length of n # is 0 then print # string not accepted if(len(n)== 0): print("string not accepted") # if 1 is found call function # stateB otherwise if 0 # is found call function stateC else: if(n[0]=='1'): stateB(n[1:]) else: stateC(n[1:]) def stateC(n): # check length of n # is 0 then print # string not accepted if(len(n)== 0): print("string not accepted") # if 1 is found call function # stateC otherwise if 0 # is found call function checkStateA else: if(n[0]=='1'): stateC(n[1:]) else: checkStateA(n[1:]) # take string input n = input() # call checkStateA # to check the inputted string checkStateA(n)
C#
// C# code for the above DFA using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function for the state A static void checkStateA(string n) { // check length of n // is 0 then print // string accepted if(n.Length == 0) Console.Write("string accepted"); // if 1 is found call function // checkStateA otherwise if 0 // is found call function stateB else { if(n[0] == '1') checkStateA(n.Substring(1)); else stateB(n.Substring(1)); } } // Function for the state B static void stateB(string n) { // check length of n // is 0 then print // string not accepted if(n.Length == 0) Console.Write("string not accepted"); // if 1 is found call function // stateB otherwise if 0 // is found call function stateC else{ if(n[0] == '1') stateB(n.Substring(1)); else stateC(n.Substring(1)); } } // Function for the state C static void stateC(string n) { // check length of n // is 0 then print // string not accepted if(n.Length == 0) Console.Write("string not accepted"); // if 1 is found call function // stateC otherwise if 0 // is found call function checkStateA else { if(n[0] == '1') stateC(n.Substring(1)); else checkStateA(n.Substring(1)); } } // Driver code public static void Main(string []args) { // take string input string n = Console.ReadLine(); // call checkStateA // to check the inputted string checkStateA(n); } } // This code is contributed by rutvik_56
Publicación traducida automáticamente
Artículo escrito por _mridul_bhardwaj_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA