Revistes Publicacions URV: Triangle - llenguatge, literatura, computació> 2012

Derivation 'Trees' and Parallelism in Chomsky-Type Grammars

  • Datos identificativos

    Identificador: RP:4411
    Handle: https://hdl.handle.net/20.500.11797/RP4411
    Autores:
    Nagy, Benedek
    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.

  • Otros:

    Autor según el artículo: Nagy, Benedek
    Palabras clave: langauge
    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.
    Año de publicación de la revista: 2012
    Tipo de publicación: info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article