DFA o Deterministic Finite Automata es una máquina de estados finitos que acepta una string (bajo alguna condición específica) si alcanza un estado final, de lo contrario la rechaza.
Problema : Dada una string de ‘0’s y ‘1’s carácter por carácter, verifique que los dos últimos caracteres sean «01» o «10»; de lo contrario, rechace la string. Imprima también el diagrama de estado independientemente de la aceptación o el rechazo. Dado que en DFA no existe el concepto de memoria, solo podemos verificar un carácter a la vez, comenzando con el carácter 0. El conjunto de entrada para este problema es {0, 1}. Para cada carácter del conjunto de entrada, cada estado de DFA se redirige a otro estado válido.
Máquina DFA : para la declaración del problema anterior, primero debemos construir una máquina DFA. La máquina DFA es similar a un diagrama de flujo con varios estados y transiciones. La máquina DFA correspondiente al problema anterior se muestra a continuación, Q3 y Q4 son los estados finales :
Ejemplos:
Input: 010101 Output: State transitions are q0->q1->q3->q4 ->q3->q4->q3->YES Explanation : 010101 ends with "01". Input: 0100 Output: State transitions are q0->q1->q3->q4->q1->NO Explanation : 0100 ends with "00", which is not equal to any of "01" or "10".
Algoritmo:
- Defina el número mínimo de estados requeridos para hacer el diagrama de estado. Use funciones para definir varios estados.
- Enumere todas las transiciones válidas. Cada estado debe tener una transición para cada símbolo válido.
- Defina los estados finales aplicando la condición base.
- Defina todas las transiciones de estado mediante llamadas a funciones de estado.
- Defina una condición de retorno para el final de la string.
Para la máquina DFA dada:
- Q0, Q1, Q2, Q3, Q4 se definen como el número de estados.
- 0 y 1 son símbolos válidos. Cada estado tiene transiciones para 0 y 1.
- Q3 y Q4 se definen como los estados finales.
- Supongamos que en el estado Q0, si llega 0, la llamada de función se realiza a Q1. Entonces, si sale 1, la llamada de función se realiza a Q2.
- Si el programa llega al final de la string, la salida se realiza de acuerdo con el estado en el que se encuentra el programa.
Implementación:
C++
// CPP Program to DFA that accepts string ending
// with 01 or 10.
#include <bits/stdc++.h>
using namespace std;
// Various states of DFA machine are defined
// using functions.
void q1(string, int);
void q2(string, int);
void q3(string, int);
void q4(string, int);
// End position is checked using the string
// length value.
// q0 is the starting state.
// q1 and q2 are intermediate states.
// q3 and q4 are final states.
void q1(string s, int i)
{
cout << "q1->";
if (i == s.length()) {
cout << "NO \n";
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s[i] == '0')
q1(s, i + 1);
else
q3(s, i + 1);
}
void q2(string s, int i)
{
cout << "q2->";
if (i == s.length()) {
cout << "NO \n";
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s[i] == '0')
q4(s, i + 1);
else
q2(s, i + 1);
}
void q3(string s, int i)
{
cout << "q3->";
if (i == s.length()) {
cout << "YES \n";
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s[i] == '0')
q4(s, i + 1);
else
q2(s, i + 1);
}
void q4(string s, int i)
{
cout << "q4->";
if (i == s.length()) {
cout << "YES \n";
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s[i] == '0')
q1(s, i + 1);
else
q3(s, i + 1);
}
void q0(string s, int i)
{
cout << "q0->";
if (i == s.length()) {
cout << "NO \n";
return;
}
// state transitions
// 0 takes to q1, 1 takes to q2
if (s[i] == '0')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Driver Code
int main()
{
string s = "010101";
// all state transitions are printed.
// if string is accpetable, YES is printed.
// else NO is printed
cout << "State transitions are ";
q0(s, 0);
}
Java
// Java Program to DFA that accepts string ending
// with 01 or 10.
class GFG
{
// End position is checked using the string
// length value.
// q0 is the starting state.
// q1 and q2 are intermediate states.
// q3 and q4 are final states.
static void q1(String s, int i)
{
System.out.print("q1->");
if (i == s.length())
{
System.out.println("NO");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s.charAt(i) == '0')
q1(s, i + 1);
else
q3(s, i + 1);
}
static void q2(String s, int i)
{
System.out.print("q2->");
if (i == s.length())
{
System.out.println("NO ");
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s.charAt(i) == '0')
q4(s, i + 1);
else
q2(s, i + 1);
}
static void q3(String s, int i)
{
System.out.print("q3->");
if (i == s.length())
{
System.out.println("YES");
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s.charAt(i) == '0')
q4(s, i + 1);
else
q2(s, i + 1);
}
static void q4(String s, int i)
{
System.out.print("q4->");
if (i == s.length())
{
System.out.println("YES");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s.charAt(i) == '0')
q1(s, i + 1);
else
q3(s, i + 1);
}
static void q0(String s, int i)
{
System.out.print("q0->");
if (i == s.length())
{
System.out.println("NO");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q2
if (s.charAt(i) == '0')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Driver Code
public static void main (String[] args)
{
String s = "010101";
// all state transitions are printed.
// if string is accpetable, YES is printed.
// else NO is printed
System.out.print("State transitions are ");
q0(s, 0);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 Program to DFA that accepts string ending
# with 01 or 10.
# End position is checked using the string
# length value.
# q0 is the starting state.
# q1 and q2 are intermediate states.
# q3 and q4 are final states.
def q1(s, i) :
print("q1->", end="");
if (i == len(s)) :
print("NO");
return;
# state transitions
# 0 takes to q1, 1 takes to q3
if (s[i] == '0') :
q1(s, i + 1);
else :
q3(s, i + 1);
def q2(s, i) :
print("q2->", end = "");
if (i == len(s)) :
print("NO");
return;
# state transitions
# 0 takes to q4, 1 takes to q2
if (s[i] == '0') :
q4(s, i + 1);
else :
q2(s, i + 1);
def q3(s, i) :
print("q3->", end = "");
if (i == len(s)) :
print("YES");
return;
# state transitions
# 0 takes to q4, 1 takes to q2
if (s[i] == '0') :
q4(s, i + 1);
else :
q2(s, i + 1);
def q4(s, i) :
print("q4->", end = "");
if (i == len(s)) :
print("YES");
return;
# state transitions
# 0 takes to q1, 1 takes to q3
if (s[i] == '0') :
q1(s, i + 1);
else :
q3(s, i + 1);
def q0( s, i) :
print("q0->", end = "");
if (i == len(s)) :
print("NO");
return;
# state transitions
# 0 takes to q1, 1 takes to q2
if (s[i] == '0') :
q1(s, i + 1);
else :
q2(s, i + 1);
# Driver Code
if __name__ == "__main__" :
s = "010101";
# all state transitions are printed.
# if string is accpetable, YES is printed.
# else NO is printed
print("State transitions are", end = " ");
q0(s, 0);
# This code is contributed by AnkitRai01
C#
// C# Program to DFA that accepts string ending
// with 01 or 10.
using System;
class GFG
{
// End position is checked using the string
// length value.
// q0 is the starting state.
// q1 and q2 are intermediate states.
// q3 and q4 are final states.
static void q1(string s, int i)
{
Console.Write("q1->");
if (i == s.Length )
{
Console.WriteLine("NO");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s[i] == '0')
q1(s, i + 1);
else
q3(s, i + 1);
}
static void q2(string s, int i)
{
Console.Write("q2->");
if (i == s.Length)
{
Console.WriteLine("NO ");
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s[i] == '0')
q4(s, i + 1);
else
q2(s, i + 1);
}
static void q3(string s, int i)
{
Console.Write("q3->");
if (i == s.Length)
{
Console.WriteLine("YES");
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s[i] == '0')
q4(s, i + 1);
else
q2(s, i + 1);
}
static void q4(string s, int i)
{
Console.Write("q4->");
if (i == s.Length)
{
Console.WriteLine("YES");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s[i] == '0')
q1(s, i + 1);
else
q3(s, i + 1);
}
static void q0(string s, int i)
{
Console.Write("q0->");
if (i == s.Length)
{
Console.WriteLine("NO");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q2
if (s[i] == '0')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Driver Code
public static void Main()
{
string s = "010101";
// all state transitions are printed.
// if string is accpetable, YES is printed.
// else NO is printed
Console.Write("State transitions are ");
q0(s, 0);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript Program to DFA that accepts string ending
// with 01 or 10.
// End position is checked using the string
// length value.
// q0 is the starting state.
// q1 and q2 are intermediate states.
// q3 and q4 are final states.
function q1(s, i) {
document.write("q1->");
if (i === s.length) {
document.write("NO");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s[i] === "0") q1(s, i + 1);
else q3(s, i + 1);
}
function q2(s, i) {
document.write("q2->");
if (i === s.length) {
document.write("NO ");
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s[i] === "0") q4(s, i + 1);
else q2(s, i + 1);
}
function q3(s, i) {
document.write("q3->");
if (i === s.length) {
document.write("YES");
return;
}
// state transitions
// 0 takes to q4, 1 takes to q2
if (s[i] === "0") q4(s, i + 1);
else q2(s, i + 1);
}
function q4(s, i) {
document.write("q4->");
if (i === s.length) {
document.write("YES");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q3
if (s[i] === "0") q1(s, i + 1);
else q3(s, i + 1);
}
function q0(s, i) {
document.write("q0->");
if (i === s.length) {
document.write("NO");
return;
}
// state transitions
// 0 takes to q1, 1 takes to q2
if (s[i] === "0") q1(s, i + 1);
else q2(s, i + 1);
}
// Driver Code
var s = "010101";
// all state transitions are printed.
// if string is accpetable, YES is printed.
// else NO is printed
document.write("State transitions are ");
q0(s, 0);
</script>
Producción:
State transitions are q0->q1->q3->q4->q3->q4->q3->YES
Complejidad: O(n) donde una string de longitud n requiere atravesar n estados.
Puede haber más de un DFA posible para una declaración de problema.
Publicación traducida automáticamente
Artículo escrito por chitrankmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA