Ambiguidade em idiomas regulares e sem contexto

Entendo que as seguintes afirmações são verdadeiras:

1. Às vezes, duas derivações distintas de uma sequência em um determinado CFG podem atribuir a mesma árvore de análise à sequência.
2. Quando existem derivações de alguma sequência em um determinado CFG que atribuem diferentes árvores de análise, o CFG é ambíguo.
3. Algumas linguagens sem contexto geradas por CFGs ambíguos também são geradas por CFGs não ambíguos.
4. Alguns idiomas são tais que os únicos CFGs que podem gerá-los (e existem alguns) são ambíguos.

Q1 Entendo também ser indecidível se um CFG arbitrário é ambíguo, no sentido do ponto 3 acima. Ou será que é indecidível se uma linguagem sem contexto é ambígua, no sentido do ponto 4? Ou ambos são indecidíveis?

Q2 Qual dos pontos 1 a 4 se torna falso quando substituímos "sem contexto" por "regular"? Gramáticas e idiomas regulares são sempre inequívocos?

Sobre o Q1: Tanto o problema de ambiguidade (dado um CFG, seja ambíguo) quanto o problema de ambiguidade inerente (dado um CFG, se seu idioma é inerentemente ambíguo, isto é, se qualquer CFG equivalente é ambíguo) é indecidível. Aqui estão as referências originais:

• A indecidibilidade da ambiguidade foi comprovada por Cantor (1962) , Floyd (1962) e Chomsky e Schützenberger (1963) . As provas nos livros didáticos geralmente são reduzidas a partir do problema de correspondência posterior.
• A indecidibilidade da ambiguidade inerente foi comprovada por Ginsburg e Ullian (1966) .

Sobre o Q2: uma gramática regular é uma gramática livre de contexto "linear unilateral", em que no máximo um não-terminal aparece em qualquer regra da parte direita da regra e onde esse não-terminal é o último (nas gramáticas lineares à direita ) ou o primeiro (em gramáticas lineares esquerdas ). Tais gramáticas são facilmente traduzidas em autômatos de estados finitos equivalentes (aproximadamente considerando cada não-terminal como um estado), que são inequívocos se a gramática regular é inequívoca. A classe de gramáticas regulares inequívocas e autômatos inequívocos foi estudada em particular por Stearns e Hunt (1985) , que mostram que eles desfrutam de algoritmos tratáveis ​​para o problema de inclusão.

1. $\beta A\gamma\Rightarrow \beta\alpha\gamma$$A\to\alpha$$A$$X_1,\dots,X_m$$A\to X_1\cdots X_m$

   $\gamma A\eta B\theta$$A$$B$$A\to\alpha$$\gamma\alpha\eta B\theta$$B\to\beta$$\gamma A\eta\beta\theta$$\gamma\alpha\eta\beta\theta$(sempre derivando o não-terminal mais à esquerda em qualquer forma sentencial) ou derivações à direita impõem uma ordem fixa para visitar as árvores de derivação e, em seguida, existe uma única derivação para uma determinada árvore de derivação.

   Em uma gramática linear livre de contexto, não existe essa opção, pois existe no máximo uma não-terminal em qualquer forma sentencial e existe uma única derivação para uma determinada árvore de derivação, que é tanto à esquerda quanto à direita.

2. $w$$w$$w$

3. e 4. Se você adota a visualização de autômatos em estado finito, basta determinar seu autômato ambíguo para obter um autômato inequívoco para o mesmo idioma: haverá uma única execução para qualquer palavra. Esse autômato determinístico é equivalente a uma gramática regular inequívoca.$~$

   $S\to A\mid B,\,A\to a,\,B\to a$$a$$S\Rightarrow A\Rightarrow a$$S\Rightarrow B\Rightarrow a$$S\to a$

$O(|G|^2)$$(q,q')$$q\neq q'$

$G$$\Sigma^*$

Eu não entendi muito bem em que tipo de idiomas você fala 4. Todo idioma do CF tem uma gramática ambígua.

Q2 Tudo é decidível se você tiver um acordo com uma gramática regular. Você só deve construir o DFA mínimo e, usando-o, você pode construir uma gramática inequívoca. Se você tem um acordo com o idioma regular definido pela gramática CF, a resposta é não - veja Q1.

Depende se você substitui 'sem contexto' por 'regular' apenas na frente de 'idioma (s)' ou também na frente de 'gramática (s)'.

Todos os idiomas regulares são gerados por gramáticas regulares e, em particular, por gramáticas regulares inequívocas, por exemplo, LL (1) gramáticas regulares à direita, que são todas inequívocas.