Portal de Periódicos da CAPES

Über die darstellbarkeit des syntaktischen monoïdes kontextfreier sprachen

1979; EDP Sciences; Volume: 13; Issue: 4 Linguagem: Francês

10.1051/ita/1979130403371

2777-3337

Günter Hotz,

Lexicography and Language Studies

Resumé.-II n'existe pas de méthode effective pour construire une présentation récursive du monoïde syntactique d'un langage algébrique à partir de la grammaire qui Vengendre.Il y a des langages « context-sensitive » L pour lesquels le problème'des mots dans le monoïde syntactique S(L) n'est pas décidable.Ceci découle du résultat plus général, que le problème des mots dans le monoïde syntactique S(L) d'un langage L décidable est lui-même décidable si S(L) a une présentation récursive.La question reste ouverte pour les langages algébriques.Soit G une grammaire algébrique réduite et 90?(G) le quotient du monoïde libre engendré par Valphabet de G par la congruence engendrée par les productions de G (prises comme relations).Si le monoïde 90? (G) est simplifiable, alors 93? (G) ne dépend que du langage L (G).Si G est «Sans impasses » (ou « à non-terminaux séparés ») alors S(L (G)) = 90?(G).Il suit alors de la première partie que le problème des mots dans S(L) est décidable.Abstract.-There are no effective Methods to construct récursive présentations for the syntactic monoid of cf.languagesfrom the gênerating grammars.There are es.languages L such that the word problemfor the syntactic monoid S(L) is not décidable.This follows from the gênerai resuit, that the word problem of the syntactic monoid S(L) of a décidable language L is décidable ifS(L) has a récursive présentation.For cf. languages this decidability question remains open.LetGbea reduced cf.grammar andSffi(G) the quotient ofthefree monoid ofthe Alphabet of G by the production system P of G.If in 90? (G) the cancellation laws hoïd, then 9CR (G) only dépends from L (G).If G is ll sackgassenfreV' then S(L (G)) = $Jl (G).It follows then from part 1 that the word problem in S(L) is décidable.