Czy istnieje rozszerzenie wyrażeń regularnych, które wychwytują języki bezkontekstowe?

25

W wielu artykułach dotyczących gramatyk bezkontekstowych (CFG), przykłady takich gramatyk tam często dopuszczają łatwą charakterystykę generowanego języka. Na przykład:

S S.zazaS.b
S.

generuje ,{za2)jabja|ja0}

S a a S b S S.zaS.b
S.zazaS.b
S.

generuje i{zajabjotjajot0}

S b S b S S.zaS.za
SbSb
S

generuje {wwRw(a|b)} lub równoważnie {((a|b))1((a|b))2p1=p2R} (gdzie p1 odnosi się do części uchwyconej przez (...)1 ).

Powyższe przykłady można wygenerować, dodając indeksy ( ), proste ograniczenia tych indeksów ( ) i dopasowanie wzorca do wyrażeń regularnych. To sprawia, że ​​zastanawiam się, czy wszystkie języki bezkontekstowe mogą być generowane przez jakieś rozszerzenie wyrażeń regularnych.zajaja>jot

Czy istnieje rozszerzenie wyrażeń regularnych, które mogą generować cały lub jakiś znaczący podzbiór języków bezkontekstowych?

Alex ten Brink
źródło
3
Zauważmy, że dodanie indeksów i ograniczeń jest zbyt mocny: będzie można zdefiniować , która nie jest CFL. zanbndon
Shaull,

Odpowiedzi:

34

Tak jest. Zdefiniuj wyrażenie bezkontekstowe jako termin generowany przez następującą gramatykę:

sol:: =ϵPusta struna|doPostać do w alfabecie Σ|solsolPowiązanie|Niepowodzenie wzoru|solsolDysjunkcja|μα.solWyrażenie gramatyczne rekurencyjne|αZmienna ekspresja

To wszystko konstruktory dla zwykłych języków oprócz gwiazdy Kleene, która jest zastąpiona przez ogólny operator stałoprzecinkowy oraz zmienny mechanizm odniesienia. (Gwiazda Kleene nie jest potrzebna, ponieważ można ją zdefiniować jako g μ α .μα.sol .)gμα.ϵgα

Interpretacja wyrażenia bezkontekstowego wymaga uwzględnienia interpretacji zmiennych swobodnych. Zdefiniuj więc środowisko jako mapę zmiennych do języków (tj. Podzbiorów Σ ) i pozwól [ ρ | α : L ] jest funkcją, która zachowuje się jak ρ na wszystkich wejściach oprócz α , i która zwraca język L dla α .ρΣ[ρ|α:L]ραLα

Teraz zdefiniuj interpretację wyrażenia bezkontekstowego w następujący sposób:

[[ϵ]]ρ={ϵ}[[c]]ρ={c}[[g1g2]]ρ={w1w2|w1[[g1]]ρw2[[g2]]ρ}[[]]ρ=[[g1g2]]ρ=[[g1]]ρ[[g2]]ρ[[α]]ρ=ρ(α)[[μα.g]]ρ=nNLnwhereL0=Ln+1=Ln[[g]][ρ|α:Ln]

Korzystając z twierdzenia Knastera-Tarskiego, łatwo zauważyć, że interpretacja jest najmniej ustalonym wyrażeniem.μα.g

To proste (choć nie do końca trywialne), aby pokazać, że możesz podać wyrażenie bezkontekstowe, wywodzące się z tego samego języka, co każda gramatyka bezkontekstowa i odwrotnie. Nietrywialność wynika z faktu, że wyrażenia bezkontekstowe mają zagnieżdżone punkty stałe, a gramatyki bezkontekstowe dają jeden stały punkt nad krotką. Wymaga to użycia lematu Bekica, który mówi dokładnie, że zagnieżdżone punkty stałe można przekształcić w pojedynczy punkt stały nad produktem (i odwrotnie). Ale to jedyna subtelność.

EDYCJA: Nie, nie znam standardowego odniesienia do tego: opracowałem to dla własnego zainteresowania. Jednak jest to na tyle oczywista konstrukcja, że ​​jestem pewien, że została wcześniej wynaleziona. Niektórzy przypadkowi Googling ujawniają niedawny artykuł Joosta Wintera, Marcello Bonsangue i Jana Ruttena Języki bezkontekstowe, Coalgebraically , w którym podają wariant tej definicji (wymagający zachowania wszystkich stałych punktów), które nazywają także wyrażeniami bezkontekstowymi.

Neel Krishnaswami
źródło
To jest całkiem niesamowite. Czy istnieje standardowa nazwa lub odniesienie do tego?
Alex ten Brink
5
Arto Salomaa opisuje to w swojej książce „Formal Languages” z 1973 r. Nazywa je „wyrażeniami regularnymi”.
Tim Schaeffer
3

Na MathOverflow pojawiło się ściśle powiązane pytanie (i kilka odpowiedzi) na temat języków, których funkcje generowania są holonomiczne .

μ

Jacques Carette
źródło
μα.sol[μα.sol/α]sol
1

Niedawno opublikowaliśmy zarys struktury, która to zrobi. Zajrzyj do comp.kompilatorów , gdzie wysłałem powiadomienie wraz z kilkoma linkami.

Nowe odkrycia działają na podstawie twierdzenia Chomsky'ego-Schuetzenbergera i można je uznać za uzupełnienie tego wyniku. Sam Chomsky został poinformowany o rozwoju sytuacji i wskazuje na chęć „nadrobienia zaległości”.

Wraz z tym rozwojem ustalamy również równoważność dwóch oddzielnych sformułowań dla wyrażeń bezkontekstowych - jednego, który jest rozszerzeniem / uzupełnieniem formy rachunku mu-najmniej „punktu stałego” (pierwotnie przez Gruska, Yntema i McWhirter) - który otrzymał ostateczną formułę w 2014 r. - a drugi opublikowano w 2008 r.

NinjaDarth
źródło
4
W odpowiedzi należy podać wszystkie istotne informacje. „Spójrz pod kompilatorami kompilacji” jest już nieprzydatną odpowiedzią i za kilka miesięcy będzie całkowicie bezużyteczne.
Emil Jeřábek wspiera Monikę
To całkowicie nie tak. Comp.kompilatory (nawiasem mówiąc, w przeciwieństwie do tej strony i innych blogów) są trwale archiwizowane. Znajdziesz tam wszystkie potrzebne szczegóły. Istnieje również wiele linków, które można tam znaleźć, w najnowszym artykule. Ponadto, w przeciwieństwie do stron blogów, jest otwarty na zewnątrz i przydatny dla znacznie szerszej publiczności. Nie powinieneś mieć trudności ze znalezieniem czegokolwiek w USENET - to właśnie tam należy kierować zapytania i omawiać takie zapytania. Jeśli masz trudności, tutaj jest link. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ
NinjaDarth
2
Problem nie polega na tym, że nie jest on archiwizowany, ale na tym, że archiwa są ogromne. Kiedy patrzę w górę archiwa teraz mogę znaleźć postu gdzieś pod górę, ale gdy ktoś zobaczy tę odpowiedź za kilka miesięcy lub lat w przyszłości, nie mają pojęcia, od czego zacząć kopać. Aroganckie i niegrzeczne jest zmuszanie czytelników do długiego i niewiarygodnego wyszukiwania, gdy można wskazać im bardziej konkretną lokalizację. Zrobiłem to dla ciebie. Zajęło to około 30 sekund. Mogłeś to zrobić sam.
Emil Jeřábek wspiera Monikę