Requisito previo: introducción de autómatas finitos , DFA de una string en la que el segundo símbolo de RHS es ‘a’
Problema: dibujar autómatas finitos deterministas (DFA) del lenguaje que contiene el conjunto de todas las strings sobre {a, b} en el que el tercer símbolo de RHS es un’.
Las strings en las que el tercer último símbolo es «a» son:
aaa, aab, aaab, aaaa, aabbaaa, bbbaba etc
El DFA que acepta el idioma de dichas strings es similar al DFA que acepta la expresión regular:
L = (a+b)*.a.(a+b).(a+b)
Por ejemplo:
Input: babaa Output: NOT ACCEPTED Input: aaabb Output: ACCEPTED
Construir directamente el DFA del problema dado es muy complicado. Entonces, aquí vamos a diseñar los autómatas finitos no deterministas (NFA) y luego convertirlos en autómatas finitos deterministas (DFA).
El NFA del idioma que contiene todas las strings en las que el tercer símbolo de la RHS es «a» es:
Aquí, A es el estado inicial y D es el estado final.
Ahora, vamos a construir la tabla de transición de estado de la NFA anterior.
Después de eso, dibujaremos la tabla de transición de estado de DFA utilizando la configuración de subconjuntos en la tabla de transición de estado de NFA. Mencionaremos todas las transiciones posibles para a y b.
Ahora es muy fácil dibujar el DFA con la ayuda de su tabla de transición. En este DFA tenemos ocho estados diferentes A, AB, AC, AD, ABC, ABD, ACD y ABCD, donde AD, ABD, ACD y ABCD son los estados finales y A es el estado inicial del DFA.
Este es nuestro DFA requerido del idioma que contiene el conjunto de todas las strings sobre {a, b} en el que el tercer símbolo de RHS es ‘a’.
Publicación traducida automáticamente
Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA