Discovering grammar of an unknown text as an optimisation problem

This paper concerns the problem of discovering an unknown grammar from a text sample. The discovering methods are formulated as optimisation problems based on a binary representation of context-sensitive grammars. The representation starts with a longest possible vector of bits to, finally, make it more compact so as to be usable in practical applications. For the sake of simplicity, considered are only noncontracting (length-preserving) grammars of order 2, excluding productions of the form P: A→ B and those deriving the empty string, i.e P: A → ε.

---

Niniejszy artykuł dotyczy problemu odkrywania nieznanej gramatyki z próbki tekstu. Metody odkrywania zostały sformułowane jako zadania optymalizacyjne oparte na binarnej reprezentacji gramatyk kontekstowych. Reprezentacja ta, początkowo jako najdłuższy możliwy wektor bitów, ostatecznie została skrócona do zwięzłej postaci, nadającej się do wykorzystania praktycznego. Dla uproszczenia uwzględniono tylko gramatyki nieskracające rzędu 2, z wyłączeniem produkcji postaci P: A→ B i tych wyprowadzających łańcuch pusty, tj. P: A → ε.