Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: gramatyka nieskracająca

Sortuj według:

Ogranicz wyniki do:

On sentence membership problem in context sensitive languages

Ryszawa P. A.

Computer Science and Mathematical Modelling

2017

No. 5

29--44

A new type of graph is introduced, the grammar graph. The possibility of assigning labels to each node in such a graph extends it to the grammar net. The grammar net should be considered as a new graphical tool that helps in an analysis of whether a particular sentence belongs to a given context-sensitive grammar. Another concept, the derivation net, closely related to the grammar graph and of a similar structure, will be used to show an algorithm that is able to decide that some sentences do not belong to a language generated by a context sensitive grammar, while leaving others as a candidate members of it.

W artykule wprowadzony został nowy rodzaj grafu – graf gramatyczny. Możliwość przypisywania etykiet do węzłów daje rozszerzenie do tzw. sieci gramatycznej. Sieć gramatyczną należy traktować jako nowe narzędzie graficzne w analizie przynależności zdań do danego języka kontekstowego. Inna koncepcja, sieć wywodu, ściśle związana z grafem gramatycznym i o podobnej strukturze, została wykorzystana do pokazania algorytmu, który potrafi wstępnie wyselekcjonować niektóre zdania nienależące do danego języka generowanego przez gramatykę kontekstową, pozostawiając inne jako potencjalnie w nim zawarte.

Discovering grammar of an unknown text as an optimisation problem

Ryszawa P. A.

Computer Science and Mathematical Modelling

2017

No. 6

15--22

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 → ε.