1. (a) Vrai, puisque tout langage régulier est sans contexte, tout langage sans contexte est décidable, et tout langage décidable est reconnaissable par Turing.
Pourquoi les langages sans contexte sont-ils décidables ?
Un problème indécidable n'a pas d'algorithme pour déterminer la réponse pour une entrée donnée Ambiguïté des langages sans contexte: étant donné un langage sans contexte, il n'y a pas de machine de Turing qui arrêtez-vous toujours dans un laps de temps fini et donnez une réponse, que la langue soit ambiguë ou non.
Le sous-ensemble d'un langage sans contexte est-il décidable ?
2 Réponses. Σ est sans contexte (en effet, c'est régulier) et il a beaucoup de sous-ensembles. Si L est un langage sans contexte de taille infinie, alors il y a des sous-ensembles J de L qui sont décidables, et certains qui sont indécidables. Par exemple, le sous-ensemble vide est décidable.
Les LCF sont-elles décidables ?
CFL: C'est décidable pour le problème de la vacuité, le problème de la finitude et le problème d'appartenance.
Combien de langues sont sans contexte ?
(1) Il existe un nombre infini de langages sans contexte. Cela est vrai parce que chaque description d'un langage sans contexte est de longueur finie, il existe donc un nombre infini de telles descriptions. (2) Il existe un nombre incalculable de langues.
