Estoy atrapado en la siguiente pregunta:
"Los lenguajes regulares son precisamente los aceptados por autómatas finitos. Dado este hecho, demuestre que si el lenguaje es aceptado por algún autómata finito, entonces también es aceptado por algún finito; consiste en todas las palabras de invertido ".
Respuestas:
Entonces, dado un lenguaje regular , sabemos (esencialmente por definición) que es aceptado por algunos autómatas finitos, por lo que hay un conjunto finito de estados con transiciones apropiadas que nos llevan del estado inicial al estado de aceptación si y solo si la entrada es una cadena en . Incluso podemos insistir en que solo hay un estado de aceptación, para simplificar las cosas. Para aceptar el lenguaje inverso, todo lo que tenemos que hacer es invertir la dirección de las transiciones, cambiar el estado de inicio a un estado de aceptación y el estado de aceptación al estado de inicio. Luego tenemos una máquina que está "al revés" en comparación con el original, y acepta el lenguaje .L L RL L LR
fuente
Usted tiene que demostrar que siempre se puede construir un autómata finito que acepta cadenas en dado un autómata finito que acepta cadenas en . Aquí hay un procedimiento para hacer eso.LR L
Formalicemos todo esto; comenzamos declarando el teorema.
Teorema. Si es un lenguaje regular, entonces también lo es .L LR
Sea ser un NFA y sea . El -NFA definido a continuación acepta el idioma .A = ( QUN, ΣUN, δUN, qUN, FUN) L = L ( A ) ϵ UNR LR
Prueba. Primero, demostramos la siguiente afirmación: una ruta de a en etiquetada con si y solo si una ruta de a en etiquetada con (el reverso de ) para . La prueba es por inducción en la longitud de .∃ q p A w ∃ p q AR wR w q,p∈QA w
Dejar y para algunos y sustituir por garantiza que . Como hay una ruta etiquetada con de a cada estado en (3. en la definición de ) y una ruta desde cada estado en al estado etiquetada con , entonces hay una ruta etiquetado con de a . Esto prueba el teorema.q=qA p=s s∈FA wR axR q∈δ∗AR(s,wR) ∀s∈FA ϵ qs FA AR FA qA wR ϵwR=wR qs qA
Tenga en cuenta que esto prueba que también.(LR)R=L
Edite si hay algún error de formato o alguna falla en mi prueba ...
fuente
Para añadir a las transformaciones basadas en autómatas descritos anteriormente, también se puede demostrar que los lenguajes regulares son cerrados bajo la inversión, mostrando cómo convertir una expresión regular para en una expresión regular para L R . Para ello, vamos a definir una función R E V en expresiones regulares que acepta como entrada una expresión regular R por lenguaje L , después produce una expresión regular R ' para el lenguaje L R . Esto se define inductivamente en la estructura de las expresiones regulares:L LR REV R L R′ LR
Puede demostrar formalmente que esta construcción es correcta como ejercicio.
¡Espero que esto ayude!
fuente
rev()
notación. :) Yo también bajéREV(R1&R2) = REV(R1)&REV(R2)
; Tengo una implementación de expresiones regulares que tiene intersección. Si; Estoy pensando en agregar un operador para la inversión tal vezR\r
(elemento regex anterior inverso).REV(~R)
es el reverso del conjunto de todas las cadenas fuera de R. ¿Es lo mismo que~REV(R)
: el conjunto de todas las cadenas fuera del reverso del conjunto denotado por R? Esto no está claro en absoluto porque también hay palíndromosR
adentroREV(R)
.Usando expresiones regulares, demuestre que si es un lenguaje regular, entonces \ emph {inversión} de L , L R = { w R : w ∈ L } , también es regular. En particular, dada una expresión regular que describe L , mostrar por inducción cómo convertir en una expresión regular que describe L R . Su prueba no debe recurrir a los NFA.L L LR={wR:w∈L} L LR
Vamos a suponer que se nos da una expresión regular que describe . Veamos primero el operador de concatenación ( ∘ ), y luego podemos pasar a operadores más avanzados. Entonces, nuestros casos de concatenación tienen que ver con la longitud de lo que se concatena. Entonces, primero romperemos todas las concatenaciones de a b a a ∘ b . Al tratar con estos, separe los componentes tanto como sea posible: ( a b ∪ a ) b → ( a b ∪ a ) ∘ bL ∘ ab a∘b (ab∪a)b→(ab∪a)∘b , pero no puede romper el orden asociativo entre diferentes comprensiones, por supuesto.
Cuando∅R→∅
Cuando , tenemos la cadena vacía que ya está invertida, por lo que el mecanismo no cambias=ϵ
Cuando es solo una letra, como en s ∈ Σ , la inversión es solo esa letra, ss s∈Σ s
Cuando , tenemos un solo componente, por lo que simplemente invertimos ese componente y, por lo tanto, σ Rs=σ σR
Cuando donde k es impar, tenemos una expresión regular que se puede escribir como ( σ 0 ∘ σ 1 . . . Σ k - 1 ∘ σ k )s=(σ0σ1...σk−1σk) (σ0∘σ1...σk−1∘σk) . La inversión de estas cadenas de longitud uniforme es simple. Simplemente cambie el índice 0 con el índice k. Luego cambie el índice 1 con el índice k-1. Continúe hasta que cada elemento se haya cambiado una vez. Por lo tanto, el último elemento es ahora el primero en el registro, y el primero es el último. El penúltimo es el segundo y el segundo es el penúltimo. Por lo tanto, tenemos un registro inverso que aceptará la cadena invertida (la primera letra es la última, etc.) Y, por supuesto, invertimos cada componente. De esta manera obtendríamos (σRkσRk−1...σR1σR0)
Cuando donde k es par, tenemos una expresión regular en general que se puede escribir como ( σ 0 ∘ σ 1 . . . σ k - 1 ∘ σ k )s=(σ0σ1...σk/2...σk−1σk) (σ0∘σ1...σk−1∘σk) . La inversión de estas cadenas de longitud uniforme es simple. Simplemente cambie el índice 0 con el índice k. Luego cambie el índice 1 con el índice k-1. Continúe hasta que cada elemento se haya cambiado una vez, pero el elemento k / 2 (un entero porque k es par). Por lo tanto, el último elemento es ahora el primero en el registro, y el primero es el último. El penúltimo es el segundo y el segundo es el penúltimo. Por lo tanto, tenemos un registro inverso que acepta la cadena invertida (la primera letra es la última, etc.). Y esa letra del medio. Y, por supuesto, revertimos cada componente. De esta manera obtendríamos (σRkσRk−1...σRk/2...σR1σR0)
De acuerdo, la parte difícil está hecha. Miremos al operador . Esto es simplemente una unión de conjuntos. Entonces, dadas dos cadenas, s 1 , s 2 , el reverso de s 1 ∪ s 2 es solo s R 1 ∪ s R 2 . La unión no cambiará. Y esto tiene sentido. Esto solo agregará cadenas a un conjunto. No importa en qué orden se agreguen al conjunto, lo único que importa es que lo sean.∪ s1,s2 s1∪s2 sR1∪sR2
El operador estrella de kleene es el mismo. Simplemente está agregando cadenas a un conjunto, sin decirnos cómo debemos interpretar el análisis de cadenas. Entonces, revertir una estrella kleene de una cadena , es solo ( ( s R ) ∗ ) . La inversión solo puede moverse a través de ellos.s ((sR)∗)
Por lo tanto, para revertir esto simplemente seguimos las reglas. Para invertir la unión externa, simplemente invertimos sus dos componentes. Para revertir esto: ( ( a ∪ b ) ∘ ( a ) ) ∗ estrella de kleene, simplemente invertimos lo que está dentro de ella → ( ( ( a(((a∪b)∘(a))∗∪((a∪b)∘(b))∗)R ((a∪b)∘(a))∗ . Luego, para revertir una concatenación, indexamos y luego cambiamos de mayor a menor. Entonces comenzamos con ( ( a ∪ b ) ∘ ( a ) ) R y obtenemos ( ( a ) R ∘ ( a ∪ b ) R ) . Para revertir esa letra única, llegamos a nuestro caso base y obtenemos ( a ) R → ( a )→(((a∪b)∘(a))R)∗ ((a∪b)∘(a))R ((a)R∘(a∪b)R) (a)R→(a) . Este proceso descrito anteriormente describe una descripción inductiva de este cambio.
fuente