On sentence membership problem in context sensitive languages

• Autorzy: Ryszawa P. A.

Warianty tytułu

PL

O problemie przynależności zdań do języków kontekstowych

• Języki publikacji: EN

Abstrakty

EN

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. 

PL

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.

Słowa kluczowe

EN

context-sensitive grammar; non-contracting grammar; formal language; graph; parsing

PL

gramatyka kontekstowa; gramatyka nieskracająca; język formalny; graf; rozbiór zdań

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Computer Science and Mathematical Modelling
• Rocznik: 2017
• Tom: No. 5
• Strony: 29--44
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Ryszawa P. A.

• Military University of Technology, Faculty of Cybernetics Kaliskiego Str. 2, 00-908 Warsaw, Poland

Bibliografia

• 1. Aho A.V., Lam M.S., Sethi R., Ullman J.D., Compilers: Principles, Techniques and Tools, 2nd Edition, Pearson Education, 2006.
• 2. Chomsky N., “On Certain Formal Properties of Grammars”, Information and Control, Vol. 2, 137–167 (1959).
• 3. Foryś M., Foryś W., Teoria automatów i języków formalnych, EXIT, 2005.
• 4. Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages and Computation, 2nd Edition, Pearson Education, 2001.
• 5. Kuroda S.-Y., “Classes of Languages and Linear-Bounded Automata”, Information and Control, Vol. 7, 207–223 (1964).
• 6. Linz P., An Introduction to Formal Languages and Automata, 5th Edition, Jones & Bartlett Learning, 2012.
• 7. Martin J.C., Introduction to Languages and the Theory of Computation, 4th Edition, McGraw-Hill, 2011.
• 8. Szwoch M., Języki formalne, automaty i translatory, PWNT, 2008.
• 9. Waite W.M., Goos G., Compiler Construction, Springer-Verlag, 1984.
• 10. Younger D.H., “Recognition and Parsing of Context-Free Grammars in Time n3”, Information and Control, Vol. 10, Issue 2, 189–208 (1967).