Derivation "Trees" and Parallelism in Chomsky-Type Grammars

Número

Sección

Articles

Autores/as

  • Benedek Nagy

Palabras clave:

language, literature, computation

Publicado

06/29/2018

Resumen

In this paper we discuss parallel derivations for context-free, contextsensitive and phrase-structure grammars. For regular and linear grammars only sequential derivation can be applied, but a kind of parallelism is present in linear grammars. We show that nite languages can be generated by a recursion-free rule-set. It is well-known that in context-free grammars the derivation can be in maximal (independent) parallel way. We show that in cases of context-sensitive and recursively enumerable languages the parallel branches of the derivation have some synchronization points. In the case of context-sensitive grammars this synchronization can only be local, but in a derivation of an arbitrary grammar we cannot make this restriction. We present a framework to show how the concept of parallelism can be t to the derivations in formal language theory using tokens.

Descargas

Agencias de apoyo

No

Cómo citar

Nagy, B. (2018). Derivation "Trees" and Parallelism in Chomsky-Type Grammars. Triangle, 8, 101-120. https://doi.org/10.17345/triangle8.101-120

Artículos más leídos del mismo autor/a

Envíos

Si desea publicar en alguna de nuestras cabeceras, debe ponerse en contacto con cada revista mediante su correo electrónico.

Saber más

Metrics

464
244
708

Desarrollado por

Palabras clave

Últimas publicaciones