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

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 \to a a S b$
$S \to$

generuje ,$\{ a^{2i} b^i | i \geq 0\}$

S → a a S b S $S \to a S b$
$S \to a a S b$
$S \to$

generuje i$\{ a^i b^j \mid i \geq j \geq 0 \}$

S → b S b S $S \to a S a$
$S \to b S b$
$S \to$

generuje $\{ w w^R \mid w \in (a|b)^* \}$ lub równoważnie $\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$ (gdzie $p_1$ 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.$a^i$$i > j$

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

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

$$\begin{array}{lcll} g & ::= & \epsilon & \mbox{Empty string}\\ & | & c & \mbox{Character $c$ in alphabet $\Sigma$} \\ & | & g \cdot g & \mbox{Concatenation} \\ & | & \bot & \mbox{Failing pattern} \\ & | & g \vee g & \mbox{Disjunction}\\ & | & \mu \alpha.\; g & \mbox{Recursive grammar expression} \\ & | & \alpha & \mbox{Variable expression} \end{array}$$

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 ∗ ≜ μ α $\mu \alpha.\;g$ .)$g\ast \triangleq \mu \alpha.\;\epsilon \vee g\cdot\alpha$

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 α .$\rho$$\Sigma^*$$[\rho|\alpha:L]$$\rho$$\alpha$$L$$\alpha$

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

$$\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}} \newcommand{\setof}[1]{\left\{#1\right\}} \newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}} \begin{array}{lcl} \interp{\epsilon}{\rho} & = & \setof{\epsilon} \\ \interp{c}{\rho} & = & \setof{c} \\ \interp{g_1\cdot g_2}{\rho} & = & \comprehend{w_1 \cdot w_2}{w_1 \in \interp{g_1}{\rho} \land w_2 \in \interp{g_2}{\rho}} \\ \interp{\bot}{\rho} & = & \emptyset \\ \interp{g_1 \vee g_2}{\rho} & = & \interp{g_1}{\rho} \cup \interp{g_2}{\rho} \\ \interp{\alpha}{\rho} & = & \rho(\alpha) \\ \interp{\mu \alpha.\; g}{\rho} & = & \bigcup_{n \in \mathbb{N}} L_n \\ \mbox{where} & & \\ L_0 & = & \emptyset \\ L_{n+1} & = & L_n \cup \interp{g}{[\rho|\alpha:L_n]} \end{array}$$

Korzystając z twierdzenia Knastera-Tarskiego, łatwo zauważyć, że interpretacja jest najmniej ustalonym wyrażeniem.$\mu \alpha.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.

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

$\mu$

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.