On sentence membership problem in context-sensitive languages
Journal Title: Computer Science and Mathematical Modelling - Year 2017, Vol 0, Issue 5
Abstract
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.
Authors and Affiliations
Paweł Ryszawa
Keywords
Related Articles
- EP ID EP231035
- DOI 10.5604/01.3001.0010.5520
- Views 123
- Downloads 0
Comparison Between Experimental, Analytical and Simulation Model of Distributed Computation on ARM processors in High-Performance Computing
The paper presents a comparison between experimental, analytical and simulation model of distributed cryptographic computation regarding password recovery with SHA 1 password hashing. The aim of this paper is compare pop...
Symulacja zachowania tłumu z użyciem modelu otoczenia opartego o graf i sieć komórek
Referat obejmuje zagadnienia związane z tworzeniem modeli i symulatorów zachowania tłumu oraz ich wykorzystaniem jako narzędzi wspomagających w procesach podejmowania decyzji. Modele i symulatory zachowania tłumu zaczęły...
Przydatność języka Gello i standardu RIM do obiektowego modelowania systemów medycznych
Współczesne systemy medyczne charakteryzują się dużą złożonością i heterogenicznością. Wymaga to ich ujednolicenia, także za pomocą standardów. Health Level 7 (HL7) jest szeroko zaakceptowanym standardem pozwalającym na...
Modele wzrostu niezawodności oprogramowania
Historia badań nad niezawodnością oprogramowania sięga lat 70. ubiegłego wieku. Od momentu pojawienia się pierwszych publikacji poświęconych tej tematyce nastąpił znaczący rozwój i postęp prac mających na celu między inn...
Usability of Gello and RIM for the object-oriented modeling of medical systems
Modern-day medical systems are complex and heterogeneous. This requires their unification, also with the help of standards. Health Level 7 (HL7) is a widely accepted standard that allows data exchange between various ins...