Dada una string que consta de los caracteres a y b , compruebe si la string comienza y termina con el mismo carácter o no. Si es así, escriba ‘Sí’; de lo contrario, escriba ‘No’.
Ejemplos:
Entrada: str = “abbaaba”
Salida: Sí
Explicación:
La string de entrada dada comienza y termina con el mismo carácter ‘a’
Por lo tanto, los estados de la siguiente máquina DFA serán q0->q1->q2->q2->q1-> q1->q2->q1 y q1 es un estado final,
por lo tanto, la salida será Sí.
Entrada: str = “ababab”
Salida: No
Explicación:
La string de entrada dada comienza y termina con un carácter diferente ‘a’ y ‘b’,
por lo que los estados de la siguiente máquina DFA serán q0->q1->q2->q1 ->q2->q1->q2 y q2 no es un estado final,
por lo que la salida será No.
Enfoque:
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.
En DFA , no existe el concepto de memoria, por lo tanto, debemos verificar la string carácter por carácter, comenzando con el carácter 0. El conjunto de caracteres de entrada para el problema es {a, b} . Para que un DFA sea válido, debe haber una regla de transición definida para cada símbolo del conjunto de entrada en cada estado a un estado válido.
Máquina DFA que acepta todas las strings que comienzan y terminan con el mismo carácter
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, Q1 y Q3 son los estados finales:
¿Cómo funciona esta máquina DFA ?
El funcionamiento de la máquina depende de si el primer carácter es ‘a’ o ‘b’.
- Caso 1: la string comienza con ‘a’
- Suponga que el primer carácter en la string de entrada es ‘a’, luego al leer ‘a’, el control cambiará a la rama superior de la máquina.
- Ahora, se define en que la string debe terminar con una ‘a’ para ser aceptada.
- En el estado Q1 , si vuelve a aparecer ‘a’, sigue dando vueltas en el mismo estado porque para la máquina el último carácter leído podría ser el último carácter de la string.
- Si obtiene una ‘b’, entonces tiene que dejar el estado final ya que una string que termina en ‘b’ no es aceptable. Entonces se mueve al estado Q2 .
- Aquí, si obtiene una ‘a’, nuevamente ingresa al estado final Q1 ; de lo contrario, para ‘b’ consecutivas, sigue dando vueltas.
- Caso 2: la string comienza con ‘b’
- Suponga que el primer carácter en la string de entrada es ‘b’, luego al leer ‘b’, el control cambiará a la rama superior de la máquina.
- Ahora, se define en que la string debe terminar con una ‘b’ para ser aceptada.
- En el estado Q3 , si vuelve a aparecer ‘b’, sigue dando vueltas en el mismo estado porque para la máquina el último carácter leído podría ser el último carácter de la string.
- Si obtiene una ‘a’, entonces tiene que dejar el estado final ya que una string que termina en ‘a’ no es aceptable. Entonces se mueve al estado Q4 .
- Aquí, si obtiene una ‘b’, nuevamente ingresa al estado final Q3 ; de lo contrario, para las ‘a’ consecutivas, sigue dando vueltas.
Enfoque para diseñar la máquina DFA:
- Defina el número mínimo de estados requeridos para hacer el diagrama de estado. Aquí Q0, Q1, Q2, Q3, Q4 son los estados definidos. Utilice funciones para varios estados.
- Enumere todas las transiciones válidas. Aquí ‘a’ y ‘b’ son símbolos válidos. Cada estado debe tener una transición para cada símbolo válido.
- Defina los estados finales aplicando la condición base. Q1 y Q3 se definen como el estado final. Si la entrada de string termina en cualquiera de estos estados, se acepta, de lo contrario se rechaza.
- Defina todas las transiciones de estado mediante llamadas a funciones de estado.
- Defina una condición de retorno para el final de la string. Si siguiendo el proceso, el programa llega al final de la string, la salida se realiza de acuerdo al estado en el que se encuentra el programa.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program for DFA that accepts string
// if it starts and ends with same character
#include <bits/stdc++.h>
using namespace std;
// States of DFA
void q1(string, int);
void q2(string, int);
void q3(string, int);
void q4(string, int);
// Function for the state Q1
void q1(string s, int i)
{
// Condition to check end of string
if (i == s.length()) {
cout << "Yes \n";
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s[i] == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q2
void q2(string s, int i)
{
// Condition to check end of string
if (i == s.length()) {
cout << "No \n";
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s[i] == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q3
void q3(string s, int i)
{
// Condition to check end of string
if (i == s.length()) {
cout << "Yes \n";
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s[i] == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q4
void q4(string s, int i)
{
// Condition to check end of string
if (i == s.length()) {
cout << "No \n";
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s[i] == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q0
void q0(string s, int i)
{
// Condition to check end of string
if (i == s.length()) {
cout << "No \n";
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q3
if (s[i] == 'a')
q1(s, i + 1);
else
q3(s, i + 1);
}
// Driver Code
int main()
{
string s = "abbaabb";
// Since q0 is the starting state
// Send the string to q0
q0(s, 0);
}
Java
// Java Program for DFA that accepts string
// if it starts and ends with same character
class GFG
{
// Function for the state Q1
static void q1(String s, int i)
{
// Condition to check end of string
if (i == s.length())
{
System.out.println("Yes");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s.charAt(i) == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q2
static void q2(String s, int i)
{
// Condition to check end of string
if (i == s.length())
{
System.out.println("No");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s.charAt(i) == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q3
static void q3(String s, int i)
{
// Condition to check end of string
if (i == s.length())
{
System.out.println("Yes");
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s.charAt(i) == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q4
static void q4(String s, int i)
{
// Condition to check end of string
if (i == s.length())
{
System.out.println("No");
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s.charAt(i) == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q0
static void q0(String s, int i)
{
// Condition to check end of string
if (i == s.length())
{
System.out.println("No");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q3
if (s.charAt(i) == 'a')
q1(s, i + 1);
else
q3(s, i + 1);
}
// Driver Code
public static void main (String[] args)
{
String s = "abbaabb";
// Since q0 is the starting state
// Send the string to q0
q0(s, 0);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 Program for DFA that accepts string
# if it starts and ends with same character
# Function for the state Q1
def q1(s, i):
# Condition to check end of string
if (i == len(s)):
print("Yes");
return;
# State transitions
# 'a' takes to q1, and
# 'b' takes to q2
if (s[i] == 'a'):
q1(s, i + 1);
else:
q2(s, i + 1);
# Function for the state Q2
def q2(s, i):
# Condition to check end of string
if (i == len(s)):
print("No");
return;
# State transitions
# 'a' takes to q1, and
# 'b' takes to q2
if (s[i] == 'a'):
q1(s, i + 1);
else:
q2(s, i + 1);
# Function for the state Q3
def q3(s, i):
# Condition to check end of string
if (i == len(s)):
print("Yes");
return;
# State transitions
# 'a' takes to q4, and
# 'b' takes to q3
if (s[i] == 'a'):
q4(s, i + 1);
else:
q3(s, i + 1);
# Function for the state Q4
def q4(s, i):
# Condition to check end of string
if (i == s.length()):
print("No");
return;
# State transitions
# 'a' takes to q4, and
# 'b' takes to q3
if (s[i] == 'a'):
q4(s, i + 1);
else:
q3(s, i + 1);
# Function for the state Q0
def q0(s, i):
# Condition to check end of string
if (i == len(s)):
print("No");
return;
# State transitions
# 'a' takes to q1, and
# 'b' takes to q3
if (s[i] == 'a'):
q1(s, i + 1);
else:
q3(s, i + 1);
# Driver Code
if __name__ == '__main__':
s = "abbaabb";
# Since q0 is the starting state
# Send the string to q0
q0(s, 0);
# This code is contributed by Rajput-Ji
C#
// C# Program for DFA that accepts string
// if it starts and ends with same character
using System;
class GFG
{
// Function for the state Q1
static void q1(string s, int i)
{
// Condition to check end of string
if (i == s.Length)
{
Console.WriteLine("Yes");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s[i] == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q2
static void q2(string s, int i)
{
// Condition to check end of string
if (i == s.Length)
{
Console.WriteLine("No");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s[i] == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q3
static void q3(string s, int i)
{
// Condition to check end of string
if (i == s.Length)
{
Console.WriteLine("Yes");
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s[i] == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q4
static void q4(string s, int i)
{
// Condition to check end of string
if (i == s.Length)
{
Console.WriteLine("No");
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s[i] == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q0
static void q0(string s, int i)
{
// Condition to check end of string
if (i == s.Length)
{
Console.WriteLine("No");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q3
if (s[i] == 'a')
q1(s, i + 1);
else
q3(s, i + 1);
}
// Driver Code
public static void Main ()
{
string s = "abbaabb";
// Since q0 is the starting state
// Send the string to q0
q0(s, 0);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript Program for DFA that accepts string
// if it starts and ends with same character
// Function for the state Q1
function q1( s, i)
{
// Condition to check end of string
if (i == s.length) {
document.write( "Yes<br>");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s[i] == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q2
function q2( s, i)
{
// Condition to check end of string
if (i == s.length) {
document.write( "No");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q2
if (s[i] == 'a')
q1(s, i + 1);
else
q2(s, i + 1);
}
// Function for the state Q3
function q3( s, i)
{
// Condition to check end of string
if (i == s.length) {
document.write( "Yes");
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s[i] == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q4
function q4( s, i)
{
// Condition to check end of string
if (i == s.length) {
document.write( "No");
return;
}
// State transitions
// 'a' takes to q4, and
// 'b' takes to q3
if (s[i] == 'a')
q4(s, i + 1);
else
q3(s, i + 1);
}
// Function for the state Q0
function q0( s, i)
{
// Condition to check end of string
if (i == s.length) {
document.write( "No");
return;
}
// State transitions
// 'a' takes to q1, and
// 'b' takes to q3
if (s[i] == 'a')
q1(s, i + 1);
else
q3(s, i + 1);
}
// Driver Code
var s = "abbaabb";
// Since q0 is the starting state
// Send the string to q0
q0(s, 0);
// This code is contributed by importantly.
</script>
Producción:
No
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por chitrankmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA