Condições suficientes para a regularidade de uma linguagem livre de contexto

Seria bom coletar uma lista de condições que impliquem que uma linguagem L sem contexto seja regular, ou seja, condições da forma: "se um CFG / PDA determinado tiver a propriedade P, suas linguagens serão regulares"

A propriedade P não precisa caracterizar os CFGs que geram idiomas regulares. Além disso, P não precisa ser decidido, e P deve "de alguma forma depender" da linguagem ser livre de contexto ("o monóide sintático de L é finito", "L é decidível no espaço o (log log n)" e, portanto, não são o que estou procurando).

reference-request fl.formal-languages regular-language context-free survey fh
fonte

parece muito provável que a questão geral seja indecidível. a analogia é que existem outros teoremas que "é B, na verdade A", onde A é uma classe de linguagem "menor" que B é indecidível. Lembro-me de uma pergunta aqui, talvez por CFLs que era semelhante, mas não consigo encontrá-la agora.

vzn

com "regularidade" você quer dizer, é realmente uma linguagem regular, certo?

vzn

ok, encontrei. esta pergunta é muito semelhante a esta "é um CFG, na verdade, uma RL" e é conhecida por ser indecidível

vzn 01/06/12

@ vzn Acho que o OP não está procurando um algoritmo para decidir a regularidade das lâmpadas fluorescentes compactas, mas sim para algumas condições suficientes. Por exemplo, a regularidade de um idioma de uma TM é indecidível, mas uma condição suficiente é que, se um idioma é decidível em , deve ser regular.

o (n l o g n)

$o(n log n)$

aelguindy

concordado, a distinção é válida. mas também é crítico saber ao mesmo tempo que o problema geral é indecidível. "condições suficientes" geralmente estão intimamente ligadas a algoritmos, por exemplo, no exemplo que você deu da complexidade do tempo (n lg n).

vzn

Respostas:

Toda linguagem livre de contexto unária é regular. (por exemplo, uma conseqüência direta do teorema de Parikh)
Se todo par iterativo / bombeado de uma linguagem livre de contexto L for degenerado , L será regular, ou seja, L será regular se, para todas as palavras x, u, y, v, z, for satisfatório: Isso foi comprovado por Ehrenfeucht, Rozenberg, "Pares iterativos fortes e a regularidade de linguagens livres de contexto ", 1983. Consulte " Linguagens livres de contexto ", de Berstel e Boasson, para uma exposição.
$x {você}^{n} y v^{n} z \in eu, para todos n \geq 0 0 ⟹ x {você}^{Eu} y v^{j} z \in eu, para todos Eu, j \geq 0$ $xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$
Se uma linguagem livre de contexto é comutativa e linear, é regular. (Ehrenfeucht, Haussler, Rozenberg, "Sobre a regularidade de línguas livres de contexto" , 1983)

fh
fonte