Est-ce que la différence de 2 contextes sans contexte est libre?

Question

J'ai cherché sur internet et la plupart disons simplement que les langages sans contexte sont fermés pour union, concaténation, inversion, et Kleene Star. Sont-ils également fermés pour la différence de set?

Answer 1

Les langues sans contexte ne sont pas fermées en cas de différence de réglage. Une façon de voir est de noter que

1. le contexte sans langues ne sont pas fermées par complémentation,
2. la langue Σ * est hors-contexte, et
3. pour tout langage L, le complément de L est donnée par Σ * - L.

par conséquent, si les lampes fluorescentes compactes ont été fermées en différence de jeu, alors ils seraient fermés sous complémentation ... sauf qu'ils ne sont pas. :-)