Utknąłem na następujące pytanie:
„Zwykłe języki są dokładnie tymi, które są akceptowane przez automaty skończone. Biorąc pod uwagę ten fakt, pokaż, że jeśli język jest akceptowany przez jakiś automat skończony, wówczas jest również akceptowany przez niektóre skończone; składa się ze wszystkich słów z odwrócone. ”
Odpowiedzi:
Zatem biorąc pod uwagę zwykły język , wiemy (zasadniczo z definicji), że jest akceptowany przez niektóre skończone automaty, więc istnieje skończony zestaw stanów z odpowiednimi przejściami, które przenoszą nas ze stanu początkowego do stanu akceptacji wtedy i tylko wtedy, gdy dane wejściowe jest ciągiem w L . Możemy nawet nalegać, aby istniał tylko jeden stan akceptacji, aby uprościć sprawy. Aby zaakceptować język zwrotny, wszystko, co musimy zrobić, to odwrócić kierunek przejść, zmienić stan początkowy na stan akceptacji i stan akceptacji na stan początkowy. Następnie mamy maszynę, która jest „do tyłu” w porównaniu do oryginału, i akceptuje język L R .L L LR
źródło
Trzeba pokazać, że zawsze można skonstruować automat skończony akceptujący ciągów wLR podane automat skończony akceptujący ciągów w L . Oto procedura, aby to zrobić.
Sformalizujmy to wszystko; zaczynamy od stwierdzenia twierdzenia.
Twierdzenie. JeśliL jest język regularny, to tak jest LR .
NiechA=(QA,ΣA,δA,qA,FA) będzie NFA i niech L=L(A) . ϵ -NFA R zdefiniowano poniżej przyjmuje język L R .AR LR
Dowód. Najpierw dowodzą następujące stwierdzenie:∃ ścieżkę z q na p w A znakowane w wtedy i tylko wtedy, gdy ∃ ścieżką od p do q w AR oznaczony wR (Odwrotna w ) do q,p∈QA . Dowodem jest indukcja na długości w .
Utrzymuje z definicji
Niech
Wiemy, że
Lettingq=qA and p=s for some s∈FA and substituting wR for axR guarantees that q∈δ∗AR(s,wR) ∀s∈FA . Since there is a path labeled with ϵ from qs to every state in FA (3. in the definition of AR ) and a path from every state in FA to the state qA labeled with wR , then there is a path labeled with ϵwR=wR from qs to qA . This proves the theorem.
Notice that this proves that(LR)R=L as well.
Please edit if there are any formatting errors or any flaws in my proof....
źródło
To add to the automata-based transformations described above, you can also prove that regular languages are closed under reversal by showing how to convert a regular expression forL into a regular expression for LR . To do so, we'll define a function REV on regular expressions that accepts as input a regular expression R for some language L , then produces a regular expression R′ for the language LR . This is defined inductively on the structure of regular expressions:
You can formally prove this construction correct as an exercise.
Hope this helps!
źródło
rev()
notation. :) I also put downREV(R1&R2) = REV(R1)&REV(R2)
; I have a regex implementation which has intersection. Yes; I'm thinking of adding an operator for reversal perhapsR\r
(reverse preceding regex element).REV(~R)
is the reverse of the set of all strings outside of R. Is that the same as~REV(R)
: the set of all strings outside of the reverse of the set denoted by R? This is not clear at all because any palindromes inR
are also inREV(R)
.Using regular expressions, prove that ifL is a regular language then the \emph{reversal} of L , LR={wR:w∈L} , is also regular. In particular, given a regular expression that describes L , show by induction how to convert it into a regular expression that describes LR . Your proof should not make recourse to NFAs.
We will assume that we are given a regular expression that describesL . Let us first look at the concatination operator (∘ ), and then we can move onto more advanced operators. So our cases of concatenation deal with the length of what is being concatenated. So first we will break all concatenations from ab to a∘b . When dealing with these break the components up as much as possible: (ab∪a)b→(ab∪a)∘b , but you cannot break associative order between different comprehensions of course.
When∅R→∅
Whens=ϵ , we have the empty string which is already reversed thus the mechanism does not change
Whens is just a letter, as in s∈Σ , the reversal is just that letter, s
Whens=σ , we have a single constituent so we just reverse that constituent and thus σR
Whens=(σ0σ1...σk−1σk) where k is odd, we have a regular expression which can be written as (σ0∘σ1...σk−1∘σk) . The reversal of these even length strings is simple. Merely switch the 0 index with the k index. Then Switch the 1 index with k-1 index. Continue till the each element was switched once. Thus the last element is now the first in the reg ex, and the first is the last. The second to last is the second and the second is the second to last. Thus we have a reversed reg ex which will accept the reversed string (first letter is the last etc.) And of course we reverse each constituent. Thus we would get (σRkσRk−1...σR1σR0)
Whens=(σ0σ1...σk/2...σk−1σk) where k is even, we have a regular expression generally which can be written as (σ0∘σ1...σk−1∘σk) . The reversal of these even length strings is simple. Merely switch the 0 index with the k index. Then Switch the 1 index with k-1 index. Continue till the each element was switched once, but the k/2 element (an integer because k is even). Thus the last element is now the first in the reg ex, and the first is the last. The second to last is the second and the second is the second to last. Thus we have a reversed reg ex which will accept the reversed string (first letter is the last etc.). And that middle letter. And of course we reverse each constituent. Thus we would get (σRkσRk−1...σRk/2...σR1σR0)
Okay the hard part is done. Let us look to the∪ operator. This is merely a union of sets. So given two strings, s1,s2 , the reverse of s1∪s2 is only sR1∪sR2 . The union will not change. And this makes sense. This will only add strings to a set. It does not matter which order they are added to the set, all that matters is that they are.
The kleene star operator is the same. It is merely adding strings to a set, not telling us how we should construt the string persay. So to reverse a kleene star of a strings , is only ((sR)∗) . Reversal can just move through them.
Thus to reverse this(((a∪b)∘(a))∗∪((a∪b)∘(b))∗)R we simply follow the rules. To reverse the outer union we simply reverse its two components. To reverse this: ((a∪b)∘(a))∗ kleene star, we simply reverse what is inside it →(((a∪b)∘(a))R)∗ . Then to reverse a concatenation, we index and then switch greatest with least. So we start with ((a∪b)∘(a))R and get ((a)R∘(a∪b)R) . To reverse that single letter, we reach our base case and get (a)R→(a) . This process outlined above describes an inductive description of this change.
źródło