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

14

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).

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
3
ok, encontrei. esta pergunta é muito semelhante a esta "é um CFG, na verdade, uma RL" e é conhecida por ser indecidível
vzn 01/06/12
4
@ 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(neuogn)
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:

15
  1. Toda linguagem livre de contexto unária é regular. (por exemplo, uma conseqüência direta do teorema de Parikh)

  2. 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.

    xvocênyvnzeu,para todos n0 0xvocêEuyvjzeu, para todos Eu,j0
  3. 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