Classe do idioma que contém apenas a sequência vazia?

7

L={ϵ}
Claramente, esse idioma é finito, portanto deve ser um idioma regular.
Agora, como toda linguagem comum é sensível ao contexto,Lé uma CSL.
Podemos definir a gramática paraL Como :
Sϵ
Agora desde Lé uma CSL, essa gramática deve ser uma gramática sensível ao contexto. Mas a partir da definição de uma gramática sensível ao contexto:

Uma gramática sensível ao contexto é qualquer gramática na qual o lado esquerdo de cada produção não exceda o lado direito.

Mas aqui
|S|>|ϵ|
Isso é contraditório.
Eu sou incapaz de descobrir o que há de errado aqui.

Romy
fonte

Respostas:

9

Esta edição é abordada no artigo da wikipedia sobre gramáticas que não contratam . Tais gramáticas não permitem derivar a string vazia, o que não é problema quando se considera idiomas.LA+. Quando se deseja permitir a sequência vazia, um caso especial é feito e a regraSλ é permitido com condições laterais feias (S não pode aparecer no lado direito).

Portanto, a situação é que existem várias definições disponíveis, a maioria equivalentes, que oferecem trocas diferentes entre elegância, generalidade, facilidade de uso, etc. Essa é uma situação típica da matemática. Quando você arranha a superfície, as diferentes definições estão lá e elas vêm com uma terminologia extra, como "essencialmente não contratantes".

Isso pode parecer confuso para os novatos, mas o lado bom é que ele separa os detalhes importantes dos não tão importantes.

BTW seu raciocínio tem uma falha. Você diz que o idioma é CSL (correto) eSλé uma gramática para isso (correta), portanto , a gramática é CS. Essa implicação está incorreta. Você só pode deduzir que existe uma gramática CS para isso. Mas você está certo ao pensar que qualquer gramática desse tipo deve ter uma regra de contratação.

phs
fonte