Czy wyrażenie regularne może być nieskończone?

Wiem, że języki, które można zdefiniować za pomocą wyrażeń regularnych i te rozpoznawane przez DFA / NFA (automaty skończone) są równoważne. Nie istnieje również DFA dla języka . Ale nadal może być napisane przy użyciu wyrażeń regularnych (zresztą każdy non-język regularny może być) jako . Wiemy jednak, że każdy język, który ma wyrażenie regularne, ma rozpoznawany przez niego DFA (sprzeczność z moim wcześniejszym stwierdzeniem). Wiem, że jest to trywialna sprawa, ale czy definicja wyrażenia regularnego obejmuje warunek, że powinien on być skończony? $\{0^n1^n|n \ge 0\}$ $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$

formal-languages regular-languages regular-expressions

— sashas
źródło

Odpowiedziałeś już na swoje pytanie: jeśli REG CFL, takie terminy nie mogą być wyrażeniami regularnymi.

⊊

$\subsetneq$

— Raphael

Wystarczy marginesie: jeśli spadnie wymóg DFA / NFA będącego skończony, że można zbudować automat do zaakceptowania

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n1^n\mid n\geq0\}$ .

Terminem automatycznym jest słowo „automata” w liczbie mnogiej „automat”. Nie ma słowa „automaty” - nie można uczynić go bardziej mnogim niż już jest. (automaty są poprawne jako zaborcze, ale nie w liczbie mnogiej)

— chasly z Wielkiej Brytanii

Odpowiedzi:

Gdyby wyrażenia regularne były nieskończone, każdy język byłby regularny.

Biorąc pod uwagę język , zawsze możemy zdefiniować wyrażenie regularne , który dokładnie określa . (Przykład: wyrażenie regularne definiuje .) $L=\{w_1, w_2, \ldots\}$ $R = w_1 + w_2 + \cdots$ $L$
$R_1 = \epsilon+0+1+00+01+10+11+\cdots$ $L_1=\{0,1\}^*$

Wiemy, że niektóre języki nie są regularne, więc pokazuje to, że nieskończone wyrażenia regularne opisują większą klasę języków niż skończone wyrażenia regularne.

— Ran G.
źródło

Uwielbiam tę odpowiedź, ponieważ nie tylko mówi, że nieskończone wyrażenia regularne są różne, ale że koncepcja w ogóle nie ma znaczenia.

— jmite

Bardziej zwięzłe stwierdzenie o punkcie, który zakopałem w drugim akapicie, a zatem jaśniejsze.

— Davislor,

Ale kończy się czystą tautologią. Dlaczego więc nie uważamy wszystkich języków za regularne, jeśli mają ten formularz? Rzeczy, które robimy z wyrażeniami regularnymi, już nie działają. Nie możemy zbudować maszyny stanów za pomocą algorytmu indukcyjnego, ponieważ nigdy się nie kończy i ma nieskończone stany. Nie możemy porównać do wszystkiego na liście i odrzucić, jeśli nic nie pasuje. I tak nie możemy fizycznie przedstawić listy. (Listy, które możemy wygenerować za pomocą komputera, są rozstrzygającymi językami.) Możemy udowodnić różne rzeczy przy użyciu tego, że każdy język ma tę formę, ale nie tego, co wiemy o wyrażeniach regularnych.

— Davislor,

@jmite „nie ma znaczenia” czy szczególny przypadek?

— BAR

@BAR Nie ma znaczenia, ponieważ w klasie języków nad opisywanych przez nieskończone wyrażenia regularne jest tylko tj. Zestaw wszystkich języków. Nie otrzymujemy klasy języków tak, jak robisz to ze skończonymi RE, CFG, a nawet maszynami Turinga.

Σ

$\Sigma$

2^{Σ}

$2^{\Sigma}$

— jmite

Tak, musi być skończony. Wyobraź sobie, że masz nieskończony zestaw możliwych dopasowań, a twój wkład to 011. Czy kiedykolwiek byłbyś w stanie to odrzucić? Czy kiedykolwiek zabraknie ci meczów do sprawdzenia?

Czy jest jakiś język, który z tej definicji nie byłby regularny ? Co z zestawem wszystkich par programów i wejść, tak że dany program zatrzymuje się na danym wejściu?

Jeśli masz program, który wylicza ciągi znaków w języku w porządku leksykograficznym -

Aktualizacja

Aby wyjaśnić nieco w oparciu o informacje zwrotne w komentarzach, powodem, dla którego nie każdy język tego formularza jest regularny, jest z definicji. Jeśli, na przykład, przejrzysz dowód twierdzenia Kleene'a, zależy to od faktu, że wyrażenie regularne musi być skończone, aby udowodnić, że generuje skończoną maszynę stanu.

Dlaczego definiujemy w ten sposób „zwykły” język? Ponieważ każdy język formalny jest podzbiorem ciągów alfabetu, a każdy zestaw ciągów może być wyrażony jako połączenie singletonów, więc jeśli nazwalibyśmy dowolny zestaw ciągów „językiem zwykłym”, zwykły język byłby po prostu synonimem język . To nie jest bardzo przydatna definicja, zwłaszcza że nie możemy jej wdrożyć w sprzęcie lub oprogramowaniu. Nie możemy nigdzie przechowywać dowolnej listy nieskończonej ani budować maszyny o nieskończonym stanie.

Jak już wspomniałem, jeśli masz sposób na wyliczenie wszystkich ciągów w języku w porządku, możesz zbudować z niego decydujący element (zaakceptuj, gdy zobaczysz dokładnie ten ciąg, odrzuć, gdy napotkasz ciąg następujący po szukają) i na odwrót (dla każdego ciągu w kolejności, uruchom go przez decider i wyślij go, jeśli tylko zostanie zaakceptowany). Tak więc, jeśli weźmiemy pod uwagę każdy wyliczalny język za regularny , każdy rozstrzygalny język byłby „regularny” i potrzebowalibyśmy nowego terminu dla języków rozpoznawanych przez maszyny skończone i ich równoważne kodowanie jako wyrażenia skończone.

— Davislor
źródło

Ta odpowiedź jest zła. Sam fakt, że pewna reprezentacja języka nie nadaje się do budowania algorytmicznego decydenta w naiwny sposób, nie oznacza, że ta reprezentacja jest błędna; mogą być inne podejścia. W rzeczywistości każdy rozstrzygający język ma reprezentację formy, którą proponuje sasha! Krótko mówiąc, popełniasz błąd „nie widzę, jak, więc musi to być niemożliwe”.

— Raphael

@Raphael: Proszę rozważyć konsekwencje swojego stwierdzenia: „ każdy rozstrzygający język ma reprezentację formy, którą proponuje Sasha!” Właśnie o to mi chodziło w mojej odpowiedzi. Pytanie brzmiało: czy wszystkie języki tego formularza są zdefiniowane jako zwykłe? Czy każdy rozstrzygający język jest regularny? (I, jak pokazałem, także niektóre nierozstrzygalne?) Czy byłaby to przydatna definicja „regularna”?

— Davislor,

Co więcej, daleki od błędnego wniosku, że nie można zrobić decydenta o nieskończonej liście ciągów, moje ostatnie zdanie było wskazówką, jak to zrobić: jeśli lista ciągów jest uporządkowana, możesz ją odrzucić jak najszybciej gdy napotkasz ciąg znaków w kolejności. Jednak maszyna stanów skończonych nie może tego zrobić, ponieważ nie może reprezentować wszystkich stanów porównania z każdym łańcuchem na nieskończonej liście, podobnie jak wyrażenia regularne. Gdyby mogli, byliby na tyle silni, aby rozpoznać wszystkie rozstrzygające języki.

— Davislor,

Załóżmy, że wyrażenia regularne mogą być nieskończone.

Zatem język zdefiniowany przez {ϵ} ∪ {01} ∪ {0011} ... będzie regularny. Dla każdego zwykłego języka istnieje NFA. Jednym ze sposobów uzyskania tego NFA byłoby posiadanie osobnych NFA dla każdego z {ϵ}, {01}, {0011} ... i łączenie ich za pomocą ϵ przejść. Ponieważ istnieją nieskończone różne wyrażenia regularne, będziemy potrzebować nieskończonych sub-NFA do połączenia. Jednak NFA może mieć tylko skończoną liczbę stanów (definicja NFA).

Zatem nie ma NFA, który mógłby zdefiniować język zdefiniowany przez połączenie nieskończonych wyrażeń regularnych, co oznacza, że język nie jest regularny.

Zatem nie ma wyrażenia regularnego, które mogłoby zdefiniować ten sam język, co język zdefiniowany przez połączenie nieskończonych wyrażeń regularnych.

Zatem wyrażenia regularne mogą mieć tylko wyrażenia skończone.

— Anurag Peshne
źródło

Twoje „nieskończone wyrażenia regularne” definiują następnie inną klasę języków, a nie regularne języki. W rzeczywistości są w stanie zdefiniować dowolny język, co jest całkowicie nieciekawe (nie są skończone, a więc ciężko z nimi pracować; i potrafią zrobić wszystko, a więc nie uczyć się w kategoriach ograniczeń).

— vonbrand,