Czy istnieje znana metoda konstruowania gramatyki przy skończonym zestawie skończonych łańcuchów?

Z mojego czytania wynika, że ​​większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót?

Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy.

Czy istnieje znana metoda wykonania tego? Idealnie nazwa techniki, którą mogę badać. Alternatywnie, jak powinienem przeszukać literaturę, aby znaleźć taką metodę?

Jest to objęte ogólnym tematem „indukcji gramatycznej”; wyszukiwanie tego wyrażenia ujawni mnóstwo literatury. Zobacz np. Indukowanie gramatyki bezkontekstowej , https://en.wikipedia.org/wiki/Grammar_induction , https://cstheory.stackexchange.com/q/27347/5038 .

W przypadku zwykłych języków (zamiast kontekstowych) zobacz także Czy regex golf NP-Complete? , Najmniejszy DFA, który akceptuje podane ciągi i odrzuca inne podane ciągi , Czy istnieją ulepszenia algorytmu Dany Angluin do uczenia się regularnych zestawów oraz https://cstheory.stackexchange.com/q/1854/5038 .

Jeśli liczba ciągów jest skończona, powiedz set $S=\{s_1,s_2....s_m\}$ zawsze możesz wymyślić gramatykę bezkontekstową, która generuje wszystkie te łańcuchy, niech $A$ być nie-terminalem, wtedy reguła może być $A \to s_1|s_2|...s_n$. Dla skończonego zestawu ciągów możesz nawet wymyślić automaty skończone, które akceptują tylko te ciągi. Tak więc przypadek skończonego zestawu ciągów jest naprawdę trywialny.

Istnieje wiele sposobów, dlatego należy nałożyć dodatkowe kryteria na jakość wyników.

1. Lista: dla każdego ciągu $w$ w języku, mieć regułę $S \rightarrow w$. Pozwolić$S$być początkowym nieterminalnym. Gotowy.
2. Drzewo prefiksów: Dla każdego prefiksu $w$ ciągu w języku, mają nieterminal $X_w$. Dla każdego ciągu$w_1xw_2$ w języku, gdzie $x$ to symbol, miej regułę $X_{w_1} \rightarrow xX_{w_2}$. Dla każdego ciągu$w$ w języku, rządzić $X_w \rightarrow \epsilon$. Pozwolić$X_\epsilon$być początkowym nieterminalnym. Gotowy.
3. Drzewo sufiksów: to samo, odwrócone.
4. Zastosowanie algorytmu gwarantuje uzyskanie gramatyki o minimalnym rozmiarze, np. Przy minimalnej liczbie reguł. Nie wiem jak to jest trudne.

To, o co pytasz, przypomina indeks wyszukiwania. Rzeczywiście, można utworzyć Przetworniki Skończonego Stanu i wykorzystywać je do rozpoznawania podawanego tekstu. Na przykład Lucene używa tego algorytmu: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

Aby uzyskać praktyczne zastosowanie, sprawdź ten post na blogu autorstwa Andrew Gallanta: Indeks 1 600 000 000 kluczy z automatami i rdzą

W poście opisuje metodę konstruowania FSA, biorąc pod uwagę zbiór tekstów, który rozpoznaje wszystkie słowa. Końcowym rezultatem jest zbudowanie w przybliżeniu minimalnego FST z wstępnie posortowanych kluczy w czasie liniowym i w stałej pamięci.

Implementacja jest dostępna w jego fstbibliotece: https://github.com/BurntSushi/fst

Odpowiedź na pytanie postawione przez reinierpost, która odpowiada również na pierwotne pytanie:

Automat konstruujemy słownik w następujący sposób:

1. zbuduj automat, który czyta i akceptuje dokładnie pierwszy ciąg.
2. dla następnego ciągu zacznij czytać go za pomocą automatu, aż do jakiejś litery nie ma przejścia. uruchom nową gałąź dla reszty łańcucha. powtarzaj, aż wszystkie łańcuchy zostaną przetworzone

Maksymalny rozmiar automatu to całkowita długość ciągów wejściowych. Zakładając, że możesz symulować przejścia i tworzyć nowe w stałym czasie, również środowisko wykonawcze jest całkowitą długością ciągów wejściowych. Brak najlepszych lub najgorszych przypadków.

Ten automat jest minimalny. ponieważ w zwykłym przypadku automaty i gramatyki odpowiadają prawie jeden do jednego, to samo dotyczy gramatyki. Oczywiście nie jest możliwe skonstruowanie czegoś o rozmiarze n w czasie krótszym niż n czasu.