Question

J'ai eu une question concernant le CNF (forme normale de Chomsky) dans la théorie du langage formel.

J'ai remarqué que de nombreux auteurs (y compris mon propre professeur et la page Wikipedia pour CNF) froncent les sourcils ou ne permettent pas au symbole de démarrage d'être sur le côté droit de la production. Cependant, je ne peux pas envelopper la tête pourquoi c'est ainsi.

Dans ces cas, ils ont fait la première étape de la conversion d'une grammaire générale sans contexte en CNF pour ajouter la production

$$ S_0 Rightarrow S $$

Mais j'ai remarqué que dans certains cas, cela conduit en fait à avoir une production inutile de plus, et dans d'autres cas, il est impossible de supprimer complètement le symbole de début complètement du côté droit des productions (à l'exclusion de la production $ S_0 Rightarrow S $). Aussi, le manuel que j'utilise (Langues formelles et automates, 6e - Peter Linz) permet au symbole de démarrage d'être sur le côté droit d'une production.

Quelle est la raison pour laquelle cette production est mal vu?

Merci.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top