Gramáticas regulares versus gramáticas livres de contexto

Estou estudando para o meu teste de linguagens de computação e há uma ideia que estou tendo problemas para entender.

Eu entendi que as gramáticas regulares são mais simples e não podem conter ambigüidade, mas não podem fazer muitas tarefas que são exigidas para linguagens de programação. Eu também entendi que gramáticas livres de contexto permitem ambigüidade, mas permitem algumas coisas necessárias para linguagens de programação (como palíndromos).

O que estou tendo problemas é entender como posso derivar todos os itens acima, sabendo que os não-terminais da gramática regular podem ser mapeados para um terminal ou um não-terminal seguido por um terminal ou que um não-terminal livre de contexto mapeia para qualquer combinação de terminais e não-terminais .

Alguém pode me ajudar a colocar tudo isso junto?

A gramática regular é linear à direita ou à esquerda, enquanto a gramática livre de contexto é basicamente qualquer combinação de terminais e não terminais. Portanto, você pode ver que a gramática regular é um subconjunto da gramática livre de contexto.

Portanto, para um palíndromo, por exemplo, é da forma,

S->ABA
A->something
B->something

Você pode ver claramente que os palíndromos não podem ser expressos na gramática regular, pois precisam ser lineares à direita ou à esquerda e, como tal, não podem ter um não terminal em ambos os lados.

Como as gramáticas regulares não são ambíguas, existe apenas uma regra de produção para um determinado não terminal, enquanto pode haver mais de uma no caso de uma gramática livre de contexto.

Acho que você quer pensar nos vários lemas do bombeamento. Uma linguagem regular pode ser reconhecida por um autômato finito. Uma linguagem livre de contexto requer uma pilha, e uma linguagem sensível ao contexto requer duas pilhas (o que é equivalente a dizer que requer uma máquina de Turing completa).

Então, se pensarmos no lema do bombeamento para linguagens regulares , o que ele diz, essencialmente, é que qualquer linguagem regular pode ser dividida em três partes, x , y e z , onde todas as instâncias da linguagem estão em xy * z (onde * é a repetição de Kleene, ou seja, 0 ou mais cópias de y .) Você basicamente tem um "não terminal" que pode ser expandido.

Agora, e quanto às linguagens livres de contexto? Há um lema de bombeamento análogo para linguagens livres de contexto que divide as strings na linguagem em cinco partes, uvxyz , e onde todas as instâncias da linguagem estão em uv ⁱ xy ⁱ z , para i ≥ 0. Agora, você tem dois "não terminais "que pode ser replicado ou bombeado, desde que você tenha o mesmo número .

A diferença entre gramática regular e livre de contexto: (N, Σ, P, S): terminais, não terminais, produções, estado inicial Símbolos terminais

● símbolos elementares da linguagem definidos por uma gramática formal

● abc

Símbolos não terminais (ou variáveis ​​sintáticas)

● substituídos por grupos de símbolos de terminais de acordo com as regras de produção

● ABC

gramática regular: gramática regular direita ou esquerda gramática regular direita, todas as regras obedecem às formas

1. B → a onde B é um não terminal em N e a é um terminal em Σ
2. B → aC onde B e C estão em N e a está em Σ
3. B → ε onde B está em N e ε denota a string vazia, ou seja, a string de comprimento 0

deixou a gramática regular, todas as regras obedecem às formas

1. A → a onde A é um não terminal em N e a é um terminal em Σ
2. A → Ba onde A e B estão em N e a está em Σ
3. A → ε onde A está em N e ε é a string vazia

gramática livre de contexto (CFG)

○ gramática formal em que toda regra de produção é da forma V → w

○ V é um único símbolo não terminal

○ w é uma string de terminais e / ou não terminais (w pode estar vazio)

Gramática regular: - gramática contendo a produção da seguinte forma é RG:

V->TV or VT
V->T

onde V = variável e T = terminal

RG pode ser Gramática do Linear Esquerdo ou Gramática do Liner Direito, mas não Gramática do Linear Médio.

Como sabemos, todos os RG são Gramática Linear, mas apenas Linear Esquerda ou Gramática Linear Direita são RG.

Uma gramática regular pode ser ambígua.

S->aA|aB
A->a
B->a

Gramática ambígua: - para uma string x existem mais de um LMD ou Mais de RMD ou Mais de uma árvore de Parse ou Um LMD e Um RMD, mas ambos produzem árvores de Parse diferentes.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

esta gramática é gramática ambígua porque dois analisam a árvore.

CFG: - Uma gramática dita CFG se sua produção estiver na forma:

   V->@   where @ belongs to (V+T)*

DCFL: - como sabemos, todos os DCFL são gramática LL (1) e todos os LL (1) são LR (1), então nunca seja ambíguo. portanto, DCFG nunca é ambíguo.

Também sabemos que todos os RL são DCFL, portanto, RL nunca seja ambíguo. Observe que RG pode ser ambíguo, mas RL não.

CFL: CFl Pode ou não ser ambíguo.

Nota: RL nunca seja inerentemente ambíguo.

Expressões regulares

• Base de análise lexical
• Representam linguagens regulares

Gramáticas livres de contexto

• Base de análise
• Representam construções de linguagem

Uma gramática é livre de contexto se todas as regras de produção tiverem a forma: A (ou seja, o lado esquerdo de uma regra só pode ser uma única variável; o lado direito é irrestrito e pode ser qualquer sequência de terminais e variáveis). Podemos definir uma gramática como uma 4 tupla, onde V é um conjunto finito (variáveis), _ é um conjunto finito (terminais), S é a variável inicial e R é um conjunto finito de regras, cada uma das quais é um mapeamento A
gramática regular V é linear à direita ou à esquerda, enquanto a gramática livre de contexto é basicamente qualquer combinação de terminais e não terminais. portanto, podemos dizer que a gramática regular é um subconjunto da gramática livre de contexto. Após essas propriedades, podemos dizer que o conjunto de Linguagens Livres de Contexto também contém o conjunto de Linguagens Regulares

Basicamente, a gramática regular é um subconjunto da gramática livre de contexto, mas não podemos dizer que Cada gramática livre de contexto é uma gramática regular. Principalmente a gramática livre de contexto é ambígua e a gramática regular pode ser ambígua.

uma gramática regular nunca é ambígua porque é linear à esquerda ou linear à direita, portanto, não podemos fazer duas árvores de decisão para a gramática regular, por isso ela é sempre inequívoca. mas, exceto a gramática regular, todos são podem ou não ser regulares