Derivation "Trees" and Parallelism in Chomsky-Type Grammars

Autores/as

  • Benedek Nagy

DOI:

https://doi.org/10.17345/triangle8.101-120

Palabras clave:

language, literature, computation

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

Los datos de descargas todavía no están disponibles.

Descargas

Publicado

06/29/2018

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

Número

Sección

Articles

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