Programa para construir un DFA que acepte strings que comiencen y terminen con un carácter diferente

Prerrequisito: Autómatas finitos deterministas 
String dada, str consta de los caracteres ‘a’ y ‘b’. La tarea es verificar si la string str comienza y termina con caracteres diferentes o no. Si es así, imprima ‘SÍ’ con transiciones de estado, de lo contrario imprima ‘NO’. 
Ejemplos: 

Entrada: ababab 
Salida: SÍ 
Explicación: 
La string «ababab» comienza con ‘a’ y termina con ‘b’
Entrada: ababa 
Salida: NO 
Explicación: 
La string «ababab» comienza con ‘a’ y termina con ‘a’ 

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: para la declaración del problema anterior, cree una 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, Q2 y Q4 son los estados finales: 
 

Explicación: 
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 que la string no 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 puede ir al estado final, ya que una string que termina en ‘b’ es aceptable en este caso, por lo que pasa al estado Q2. Aquí, si obtiene una ‘a’, nuevamente ingresa al estado no final; de lo contrario, para las ‘b’ consecutivas, sigue dando vueltas en el estado final. 
Lo mismo ocurre en el caso de que el primer carácter se detecte como ‘b’.
Acercarse: 

1. Defina el número mínimo de estados requeridos para hacer el diagrama de estado. Utilice funciones para varios estados.
2. Enumere todas las transiciones válidas. Cada estado debe tener una transición para cada símbolo válido.
3. Defina los estados finales aplicando la condición base.
4. Defina todas las transiciones de estado mediante llamadas a funciones de estado.
5. Defina una condición de retorno para el final de la string.

Para la máquina DFA dada, las especificaciones son las siguientes: 

1. Q0, Q1, Q2, Q3, Q4 son los estados definidos.
2. a y b son símbolos válidos. Cada estado tiene una transición definida para a y b.
3. Q2 y Q4 se definen como el estado final. Si la entrada de string termina en cualquiera de estos estados, se acepta, de lo contrario se rechaza.
4. Supongamos que en el estado Q0, si viene ‘a’, la llamada de función se realiza a Q1. Si viene ‘b’, la llamada de función se hace a Q3.
5. 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: 
 

// CPP Program to DFA that accepts
// string if it starts and end with
// same character
#include <bits/stdc++.h>
using namespace std;
 
// various states of DFA machine
// are defined using functions.
bool q1(string, int);
bool q2(string, int);
bool q3(string, int);
bool q4(string, int);
 
// vector to store state transition
vector<string> state_transition;
 
// end position is checked using string
// length value.
// q0 is the starting state.
// q2 and q4 are intermediate states.
// q1 and q3 are final states.
 
bool q1(string s, int i)
{
    state_transition.push_back("q1");
    if (i == s.length()) {
        return false;
    }
 
    // state transitions
    // a takes to q1, b takes to q2
    if (s[i] == 'a')
        return q1(s, i + 1);
    else
        return q2(s, i + 1);
}
 
bool q2(string s, int i)
{
    state_transition.push_back("q2");
    if (i == s.length()) {
        return true;
    }
 
    // state transitions
    // a takes to q1, b takes to q2
    if (s[i] == 'a')
        return q1(s, i + 1);
    else
        return q2(s, i + 1);
}
 
bool q3(string s, int i)
{
    state_transition.push_back("q3");
    if (i == s.length()) {
        return false;
    }
 
    // state transitions
    // a takes to q4, 1 takes to q3
    if (s[i] == 'a')
        return q4(s, i + 1);
    else
        return q3(s, i + 1);
}
 
bool q4(string s, int i)
{
    state_transition.push_back("q4");
    if (i == s.length()) {
        return true;
    }
 
    // state transitions
    // a takes to q4, b takes to q3
    if (s[i] == 'a')
        return q4(s, i + 1);
    else
        return q3(s, i + 1);
}
 
bool q0(string s, int i)
{
    state_transition.push_back("q0");
    if (i == s.length()) {
        return false;
    }
 
    // state transitions
    // a takes to q1, b takes to q3
    if (s[i] == 'a')
        return q1(s, i + 1);
    else
        return q3(s, i + 1);
}
 
int main()
{
    string s = "ababab";
 
    // all state transitions are printed.
    // if string is acceptable, print YES.
    // else NO is printed
    bool ans = q0(s, 0);
    if (ans) {
        cout << "YES" << endl;
 
        // print transition state of given
        // string str
        for (auto& it : state_transition) {
            cout << it << ' ';
        }
    }
    else
        cout << "NO" << endl;
    return 0;
}

// Java Program to DFA that accepts
// string if it starts and end with
// same character
import java.util.*;
 
class GFG
{
     
    // vector to store state transition
    static Vector state_transition = new Vector();
     
    // end position is checked using string
    // length value.
    // q0 is the starting state.
    // q2 and q4 are intermediate states.
    // q1 and q3 are final states.
     
    static boolean q1(String s, int i)
    {
        state_transition.add("q1");
        if (i == s.length())
        {
            return false;
        }
     
        // state transitions
        // a takes to q1, b takes to q2
        if (s.charAt(i) == 'a')
            return q1(s, i + 1);
        else
            return q2(s, i + 1);
    }
     
    static boolean q2(String s, int i)
    {
        state_transition.add("q2");
        if (i == s.length())
        {
            return true;
        }
     
        // state transitions
        // a takes to q1, b takes to q2
        if (s.charAt(i) == 'a')
            return q1(s, i + 1);
        else
            return q2(s, i + 1);
    }
     
    static boolean q3(String s, int i)
    {
        state_transition.add("q3");
        if (i == s.length())
        {
            return false;
        }
     
        // state transitions
        // a takes to q4, 1 takes to q3
        if (s.charAt(i) == 'a')
            return q4(s, i + 1);
        else
            return q3(s, i + 1);
    }
     
    static boolean q4(String s, int i)
    {
        state_transition.add("q4");
        if (i == s.length())
        {
            return true;
        }
     
        // state transitions
        // a takes to q4, b takes to q3
        if (s.charAt(i) == 'a')
            return q4(s, i + 1);
        else
            return q3(s, i + 1);
    }
     
    static boolean q0(String s, int i)
    {
        state_transition.add("q0");
        if (i == s.length())
        {
            return false;
        }
     
        // state transitions
        // a takes to q1, b takes to q3
        if (s.charAt(i) == 'a')
            return q1(s, i + 1);
        else
            return q3(s, i + 1);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String s = "ababab";
     
        // all state transitions are printed.
        // if string is acceptable, print YES.
        // else NO is printed
        boolean ans = q0(s, 0);
        if (ans == true)
        {
            System.out.println("YES");
     
            // print transition state of given
            // string str
            for(int index = 0; index < state_transition.size(); index++)
            { //(auto& it : ) {
                System.out.print((String)state_transition.get(index) + ' ');
            }
        }
        else
            System.out.println("NO");
    }
}
 
// This code is contributed by AnkitRai01

# Python3 Program to DFA that accepts
# if it starts and end with
# same character
 
 
# vector to store state transition
state_transition = []
 
# end position is checked using string
# length value.
# q0 is the starting state.
# q2 and q4 are intermediate states.
# q1 and q3 are final states.
def q1(s, i):
 
    state_transition.append("q1")
    if (i == len(s)):
        return False
 
    # state transitions
    # a takes to q1, b takes to q2
    if (s[i] == 'a'):
        return q1(s, i + 1)
    else:
        return q2(s, i + 1)
 
def q2(s, i):
 
    state_transition.append("q2")
    if (i == len(s)):
        return True
 
    # state transitions
    # a takes to q1, b takes to q2
    if (s[i] == 'a'):
        return q1(s, i + 1)
    else:
        return q2(s, i + 1)
 
def q3(s, i):
 
    state_transition.append("q3")
    if (i == len(s)):
        return False
 
    # state transitions
    # a takes to q4, 1 takes to q3
    if (s[i] == 'a'):
        return q4(s, i + 1)
    else:
        return q3(s, i + 1)
 
def q4(s, i):
 
    state_transition.append("q4")
    if (i == len(s)):
        return True
 
    # state transitions
    # a takes to q4, b takes to q3
    if (s[i] == 'a'):
        return q4(s, i + 1)
    else:
        return q3(s, i + 1)
 
def q0(s, i):
 
    state_transition.append("q0")
    if (i == len(s)):
        return False
 
    # state transitions
    # a takes to q1, b takes to q3
    if (s[i] == 'a'):
        return q1(s, i + 1)
    else:
        return q3(s, i + 1)
 
s = "ababab"
 
# all state transitions are printed.
# if is acceptable, print YES.
# else NO is printed
ans = q0(s, 0)
if (ans):
    print("YES")
 
    # print transition state of given
    # str
    for it in state_transition:
        print(it, end = " ")
 
else:
    print("NO")
 
# This code is contributed by mohit kumar 29

// C# Program to DFA that accepts
// string if it starts and end with
// same character
using System;
using System.Collections;
class GFG{
      
// vector to store state transition
static ArrayList state_transition =
                 new ArrayList();
      
// end position is checked using
// string length value.
// q0 is the starting state.
// q2 and q4 are intermediate
// states. q1 and q3 are final
// states.     
static bool q1(string s, int i)
{
  state_transition.Add("q1");
  if (i == s.Length)
  {
    return false;
  }
 
  // state transitions
  // a takes to q1, b
  // takes to q2
  if (s[i] == 'a')
    return q1(s, i + 1);
  else
    return q2(s, i + 1);
}
 
static bool q2(string s, int i)
{
  state_transition.Add("q2");
  if (i == s.Length)
  {
    return true;
  }
 
  // state transitions
  // a takes to q1, b takes to q2
  if (s[i] == 'a')
    return q1(s, i + 1);
  else
    return q2(s, i + 1);
}
      
static bool q3(string s, int i)
{
  state_transition.Add("q3");
  if (i == s.Length)
  {
    return false;
  }
 
  // state transitions
  // a takes to q4, 1
  // takes to q3
  if (s[i] == 'a')
    return q4(s, i + 1);
  else
    return q3(s, i + 1);
}
      
static bool q4(string s, int i)
{
  state_transition.Add("q4");
  if (i == s.Length)
  {
    return true;
  }
 
  // state transitions
  // a takes to q4, b
  // takes to q3
  if (s[i] == 'a')
    return q4(s, i + 1);
  else
    return q3(s, i + 1);
}
      
static bool q0(string s, int i)
{
  state_transition.Add("q0");
  if (i == s.Length)
  {
    return false;
  }
 
  // state transitions
  // a takes to q1, b
  // takes to q3
  if (s[i] == 'a')
    return q1(s, i + 1);
  else
    return q3(s, i + 1);
}
      
// Driver code
public static void Main (string[] args)
{
  string s = "ababab";
 
  // all state transitions are
  // printed. If string is
  // acceptable, print YES.
  // else NO is printed
  bool ans = q0(s, 0);
 
  if (ans == true)
  {
    Console.Write("YES\n");
 
    // print transition state
    // of given string str
    for(int index = 0;
            index < state_transition.Count;
            index++)
    {
      //(auto& it : ) {
      Console.Write(
      (string)state_transition[index] + ' ');
    }
  }
  else
    Console.Write("NO");
}
}
 
// This code is contributed bt rutvik_56

<script>
      // JavaScript Program to DFA that accepts
      // string if it starts and end with
      // same character
      // vector to store state transition
      var state_transition = [];
 
      // end position is checked using
      // string length value.
      // q0 is the starting state.
      // q2 and q4 are intermediate
      // states. q1 and q3 are final
      // states.
      function q1(s, i) {
        state_transition.push("q1");
        if (i === s.length) {
          return false;
        }
 
        // state transitions
        // a takes to q1, b
        // takes to q2
        if (s[i] === "a") return q1(s, i + 1);
        else return q2(s, i + 1);
      }
 
      function q2(s, i) {
        state_transition.push("q2");
        if (i === s.length) {
          return true;
        }
 
        // state transitions
        // a takes to q1, b takes to q2
        if (s[i] === "a") return q1(s, i + 1);
        else return q2(s, i + 1);
      }
 
      function q3(s, i) {
        state_transition.push("q3");
        if (i === s.length) {
          return false;
        }
 
        // state transitions
        // a takes to q4, 1
        // takes to q3
        if (s[i] === "a") return q4(s, i + 1);
        else return q3(s, i + 1);
      }
 
      function q4(s, i) {
        state_transition.push("q4");
        if (i === s.length) {
          return true;
        }
 
        // state transitions
        // a takes to q4, b
        // takes to q3
        if (s[i] === "a") return q4(s, i + 1);
        else return q3(s, i + 1);
      }
 
      function q0(s, i) {
        state_transition.push("q0");
        if (i === s.length) {
          return false;
        }
 
        // state transitions
        // a takes to q1, b
        // takes to q3
        if (s[i] === "a") return q1(s, i + 1);
        else return q3(s, i + 1);
      }
 
      // Driver code
      var s = "ababab";
 
      // all state transitions are
      // printed. If string is
      // acceptable, print YES.
      // else NO is printed
      var ans = q0(s, 0);
 
      if (ans === true) {
        document.write("YES <br>");
 
        // print transition state
        // of given string str
        for (var index = 0; index < state_transition.length; index++) {
          //(auto& it : ) {
          document.write(state_transition[index] + " ");
        }
      } else document.write("NO");
       
      // This code is contributed by rdtank.
    </script>

YES
q0 q1 q2 q1 q2 q1 q2

Complejidad de tiempo: O (n) donde una string de longitud n requiere atravesar n estados.