Problema: acepte strings que no terminen con la substring «EL». Compruebe si una string dada termina con «el» o no. Las diferentes formas de “the” que se evitan al final de la string son:
"THE", "ThE", "THe", "tHE", "thE", "The", "tHe" and "the"
No se aceptan todas aquellas strings que terminan con cualquiera de las formas mencionadas anteriormente de «the».
Autómatas finitos deterministas (DFA) de strings que no terminan con «THE»:
el estado inicial y de inicio en este dfa es Qo
Enfoque utilizado en el programa:
en este programa, considere que los 4 estados son 0, 1, 2 y 3. Ahora tomemos una variable llamada DFA que inicialmente será 0. Cada vez que se produzca una transición, actualizará el valor de DFA con el número asociado con el nuevo estado.
Ejemplo: si ocurre una transición del estado 0 al estado 1, el valor de DFA se actualizará a 1. Si ocurre una transición del estado 2 al estado 3, el valor de dfa se actualizará a 3. De esta manera, aplique esto algoritmo en toda la string y, si al final, alcanza el estado 0, 1 o 2, nuestra string será aceptada; de lo contrario, no.
Input : XYzabCthe Output : NOT ACCEPTED Input : Themaliktth Output : ACCEPTED
C++
// C++ program to implement DFS that accepts
// all string that do not end with "THE"
#include <iostream>
using namespace std;
// dfa tells the number associated
// with the present state
int dfa = 0;
// This function is for
// the starting state (zeroth) of DFA
void start(char c)
{
// On receiving 'T' or 't' goto
// first state (1)
if (c == 't' || c == 'T')
dfa = 1;
}
// This function is for the first state of DFA
void state1(char c)
{
// On receiving 'T' or 't' goto
// first state (1)
if (c == 't' || c == 'T')
dfa = 1;
// On receiving 'H' or 'h'
// goto second state (2)
else if (c == 'h' || c == 'H')
dfa = 2;
// Else goto starting state (0)
else
dfa = 0;
}
// This function is for the second state of DFA
void state2(char c)
{
// On receiving 'E' or 'e' goto third state (3)
// else goto starting state (0)
if (c == 'e' || c == 'E')
dfa = 3;
else if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
// This function is for the third state of DFA
void state3(char c)
{
// On receiving 'T' or 't' goto first state (1)
// else goto starting state (0)
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
bool isAccepted(string str)
{
// Store length of string
int len = str.length();
for(int i = 0; i < len; i++)
{
if (dfa == 0)
start(str[i]);
else if (dfa == 1)
state1(str[i]);
else if (dfa == 2)
state2(str[i]);
else
state3(str[i]);
}
return (dfa != 3);
}
// Driver code
int main()
{
string str = "forTHEgeeks";
if (isAccepted(str) == true)
cout << "ACCEPTED\n";
else
cout << "NOT ACCEPTED\n";
return 0;
}
// This code is contributed by ShubhamSingh10
C
// C program to implement DFS that accepts
// all string that do not end with "THE"
#include <stdio.h>
#include <string.h>
// dfa tells the number associated
// with the present state
int dfa = 0;
// This function is for
// the starting state (zeroth) of DFA
void start(char c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
}
// This function is for the first state of DFA
void state1(char c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
// On receiving 'H' or 'h' goto second state (2)
else if (c == 'h' || c == 'H')
dfa = 2;
// else goto starting state (0)
else
dfa = 0;
}
// This function is for the second state of DFA
void state2(char c)
{
// On receiving 'E' or 'e' goto third state (3)
// else goto starting state (0)
if (c == 'e' || c == 'E')
dfa = 3;
else if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
// This function is for the third state of DFA
void state3(char c)
{
// On receiving 'T' or 't' goto first state (1)
// else goto starting state (0)
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
bool isAccepted(char str[])
{
// store length of string
int len = strlen(str);
for (int i=0; i < len; i++) {
if (dfa == 0)
start(str[i]);
else if (dfa == 1)
state1(str[i]);
else if (dfa == 2)
state2(str[i]);
else
state3(str[i]);
}
return (dfa != 3);
}
// driver code
int main()
{
char str[] = "forTHEgeeks";
if (isAccepted(str) == true)
printf("ACCEPTED\n");
else
printf("NOT ACCEPTED\n");
return 0;
}
Java
// Java program to implement DFS that accepts
// all string that do not end with "THE"
import java.util.*;
class GFG
{
// dfa tells the number associated
// with the present state
static int dfa = 0;
// This function is for
// the starting state (zeroth) of DFA
static void start(char c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
}
// This function is for the first state of DFA
static void state1(char c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
// On receiving 'H' or 'h' goto second state (2)
else if (c == 'h' || c == 'H')
dfa = 2;
// else goto starting state (0)
else
dfa = 0;
}
// This function is for the second state of DFA
static void state2(char c)
{
// On receiving 'E' or 'e' goto third state (3)
// else goto starting state (0)
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
// This function is for the third state of DFA
static void state3(char c)
{
// On receiving 'T' or 't' goto first state (1)
// else goto starting state (0)
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
static boolean isAccepted(char str[])
{
// store length of string
int len = str.length;
for (int i=0; i < len; i++)
{
if (dfa == 0)
start(str[i]);
else if (dfa == 1)
state1(str[i]);
else if (dfa == 2)
state2(str[i]);
else
state3(str[i]);
}
return (dfa != 3);
}
// Driver code
public static void main(String[] args)
{
char str[] = "forTHEgeeks".toCharArray();
if (isAccepted(str) == true)
System.out.println("ACCEPTED\n");
else
System.out.println("NOT ACCEPTED\n");
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python3 program to implement DFS that accepts
# all stringing that do not end with "THE"
# This function is for the starting
# state (zeroth) of DFA
def start(c):
# On receiving 'T' or 't' goto
# first state (1)
if (c == 't' or c == 'T'):
dfa=1
# This function is for the first state of DFA
def state1(c):
# On receiving 'T' or 't' goto first state (1)
if (c == 't' or c == 'T'):
dfa = 1
# On receiving 'H' or 'h' goto second state (2)
elif (c == 'h' or c == 'H'):
dfa = 2
# else goto starting state (0)
else:
dfa = 0
# This function is for the second state of DFA
def state2(c):
# On receiving 'E' or 'e' goto third
# state (3) else goto starting state (0)
if (c == 'e' or c == 'E'):
dfa = 3
else:
dfa = 0
# This function is for the third state of DFA
def state3(c):
# On receiving 'T' or 't' goto first
# state (1) else goto starting state (0)
if (c == 't' or c == 'T'):
dfa = 1
else:
dfa = 0
def isAccepted(string):
# store length of stringing
length = len(string)
for i in range(length):
if (dfa == 0):
start(string[i])
elif (dfa == 1):
state1(string[i])
elif (dfa == 2):
state2(string[i])
else:
state3(string[i])
return (dfa != 3)
# Driver Code
if __name__ == "__main__" :
string="forTHEgeeks"
# dfa tells the number associated
# with the present state
dfa = 0
if isAccepted(string):
print("ACCEPTED")
else:
print("NOT ACCEPTED")
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to implement DFS that accepts
// all string that do not end with "THE"
using System;
class GFG
{
// dfa tells the number associated
// with the present state
static int dfa = 0;
// This function is for
// the starting state (zeroth) of DFA
static void start(char c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
}
// This function is for the first state of DFA
static void state1(char c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
// On receiving 'H' or 'h' goto second state (2)
else if (c == 'h' || c == 'H')
dfa = 2;
// else goto starting state (0)
else
dfa = 0;
}
// This function is for the second state of DFA
static void state2(char c)
{
// On receiving 'E' or 'e' goto third state (3)
// else goto starting state (0)
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
// This function is for the third state of DFA
static void state3(char c)
{
// On receiving 'T' or 't' goto first state (1)
// else goto starting state (0)
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
static bool isAccepted(char []str)
{
// store length of string
int len = str.Length;
for (int i=0; i < len; i++)
{
if (dfa == 0)
start(str[i]);
else if (dfa == 1)
state1(str[i]);
else if (dfa == 2)
state2(str[i]);
else
state3(str[i]);
}
return (dfa != 3);
}
// Driver code
static public void Main ()
{
char []str = "forTHEgeeks".ToCharArray();
if (isAccepted(str) == true)
Console.WriteLine("ACCEPTED\n");
else
Console.WriteLine("NOT ACCEPTED\n");
}
}
/* This code is contributed by ajit. */
PHP
<?php
// PHP program to implement DFS
// that accepts all string that
// do not end with "THE"
// dfa tells the number associated
// with the present state
$dfa = 0;
// This function is for the
// starting state (zeroth) of DFA
function start($c)
{
global $dfa;
// On receiving 'T' or 't'
// goto first state (1)
if ($c == 't' || $c == 'T')
$dfa = 1;
}
// This function is for
// the first state of DFA
function state1($c)
{
global $dfa;
// On receiving 'T' or 't'
// goto first state (1)
if ($c == 't' || $c == 'T')
$dfa = 1;
// On receiving 'H' or 'h'
// goto second state (2)
else if ($c == 'h' || $c == 'H')
$dfa = 2;
// else goto starting state (0)
else
$dfa = 0;
}
// This function is for
// the second state of DFA
function state2($c)
{
global $dfa;
// On receiving 'E' or 'e'
// goto third state (3) else
// goto starting state (0)
if ($c == 'e' || $c == 'E')
$dfa = 3;
else
$dfa = 0;
}
// This function is for
// the third state of DFA
function state3($c)
{
global $dfa;
// On receiving 'T' or 't'
// goto first state (1) else
// goto starting state (0)
if ($c == 't' || $c == 'T')
$dfa = 1;
else
$dfa = 0;
}
function isAccepted($str)
{
global $dfa;
// store length of string
$len = strlen($str);
for ($i=0; $i < $len; $i++)
{
if ($dfa == 0)
start($str[$i]);
else if ($dfa == 1)
state1($str[$i]);
else if ($dfa == 2)
state2($str[$i]);
else
state3($str[$i]);
}
return ($dfa != 3);
}
// Driver Code
$str = "forTHEgeeks";
if (isAccepted($str) == true)
echo "ACCEPTED\n";
else
echo "NOT ACCEPTED\n";
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to
// implement DFS that accepts
// all string that do not end
// with "THE"
// dfa tells the number associated
// with the present state
let dfa = 0;
// This function is for
// the starting state (zeroth) of DFA
function start(c)
{
// On receiving 'T' or 't' goto
// first state (1)
if (c == 't' || c == 'T')
dfa = 1;
}
// This function is for the first state of DFA
function state1(c)
{
// On receiving 'T' or 't' goto first state (1)
if (c == 't' || c == 'T')
dfa = 1;
// On receiving 'H' or 'h' goto second state (2)
else if (c == 'h' || c == 'H')
dfa = 2;
// else goto starting state (0)
else
dfa = 0;
}
// This function is for the second state of DFA
function state2(c)
{
// On receiving 'E' or 'e' goto third state (3)
// else goto starting state (0)
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
// This function is for the third state of DFA
function state3(c)
{
// On receiving 'T' or 't' goto first state (1)
// else goto starting state (0)
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
function isAccepted(str)
{
// store length of string
let len = str.length;
for (let i=0; i < len; i++)
{
if (dfa == 0)
start(str[i]);
else if (dfa == 1)
state1(str[i]);
else if (dfa == 2)
state2(str[i]);
else
state3(str[i]);
}
return (dfa != 3);
}
let str = "forTHEgeeks".split('');
if (isAccepted(str) == true)
document.write("ACCEPTED");
else
document.write("NOT ACCEPTED");
</script>
Producción :
ACCEPTED
La complejidad temporal de este programa es O(n)
Publicación traducida automáticamente
Artículo escrito por RishabhMalik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA