Simplificação CFG
Em uma CFG, pode acontecer que todas as regras de produção e símbolos não sejam necessários para a derivação de strings. Além disso, pode haver algumas produções nulas e produções unitárias. A eliminação dessas produções e símbolos é chamadasimplification of CFGs. A simplificação compreende essencialmente as seguintes etapas -
- Redução de CFG
- Remoção de unidades de produção
- Remoção de produções nulas
Redução de CFG
CFGs são reduzidos em duas fases -
Phase 1 - Derivação de uma gramática equivalente, G’, do CFG, G, de modo que cada variável derive alguma string terminal.
Derivation Procedure -
Etapa 1 - Incluir todos os símbolos, W1, que derivam algum terminal e inicializam i=1.
Etapa 2 - Incluir todos os símbolos, Wi+1, que derivam Wi.
Etapa 3 - Incremento i e repita a Etapa 2, até Wi+1 = Wi.
Etapa 4 - Incluir todas as regras de produção que têm Wi iniciar.
Phase 2 - Derivação de uma gramática equivalente, G”, do CFG, G’, de modo que cada símbolo apareça em uma forma sentencial.
Derivation Procedure -
Etapa 1 - Incluir o símbolo de início em Y1 e inicializar i = 1.
Etapa 2 - Incluir todos os símbolos, Yi+1, que pode ser derivado de Yi e incluir todas as regras de produção que foram aplicadas.
Etapa 3 - Incremento i e repita a Etapa 2, até Yi+1 = Yi.
Problema
Encontre uma gramática reduzida equivalente à gramática G, com regras de produção, P: S → AC | B, A → a, C → c | BC, E → aA | e
Solução
Phase 1 -
T = {a, c, e}
W 1 = {A, C, E} das regras A → a, C → c e E → aA
W 2 = {A, C, E} U {S} da regra S → AC
W 3 = {A, C, E, S} U ∅
Como W 2 = W 3 , podemos derivar G 'como -
G '= {{A, C, E, S}, {a, c, e}, P, {S}}
onde P: S → AC, A → a, C → c, E → aA | e
Phase 2 -
Y 1 = {S}
Y 2 = {S, A, C} da regra S → AC
Y 3 = {S, A, C, a, c} das regras A → a e C → c
Y 4 = {S, A, C, a, c}
Uma vez que Y 3 = Y 4 , podemos derivar G ”como -
G ”= {{A, C, S}, {a, c}, P, {S}}
onde P: S → AC, A → a, C → c
Remoção de unidades de produção
Qualquer regra de produção na forma A → B onde A, B ∈ não terminal é chamada unit production..
Procedimento de Remoção -
Step 1 - Para remover A → B, adicionar produção A → x à regra gramatical sempre que B → xocorre na gramática. [x ∈ Terminal, x pode ser Nulo]
Step 2 - Apagar A → B da gramática.
Step 3 - Repita a partir da etapa 1 até que todas as unidades de produção sejam removidas.
Problem
Remova a unidade de produção do seguinte -
S → XY, X → a, Y → Z | b, Z → M, M → N, N → a
Solution -
Existem 3 produções unitárias na gramática -
Y → Z, Z → M e M → N
At first, we will remove M → N.
Como N → a, adicionamos M → a, e M → N é removido.
O conjunto de produção torna-se
S → XY, X → a, Y → Z | b, Z → M, M → a, N → a
Now we will remove Z → M.
Como M → a, adicionamos Z → a, e Z → M é removido.
O conjunto de produção torna-se
S → XY, X → a, Y → Z | b, Z → a, M → a, N → a
Now we will remove Y → Z.
Como Z → a, adicionamos Y → a, e Y → Z é removido.
O conjunto de produção torna-se
S → XY, X → a, Y → a | b, Z → a, M → a, N → a
Agora Z, M e N estão inacessíveis, portanto, podemos removê-los.
O CFG final é uma unidade de produção livre -
S → XY, X → a, Y → a | b
Remoção de produções nulas
Em um CFG, um símbolo não terminal ‘A’ é uma variável anulável se houver uma produção A → ε ou há uma derivação que começa em A e finalmente termina com
ε: A → .......… → ε
Procedimento de Remoção
Step 1 - Descubra variáveis não terminais anuláveis que derivam ε.
Step 2 - Para cada produção A → a, construir todas as produções A → x Onde x é obtido de ‘a’ removendo um ou vários não terminais da Etapa 1.
Step 3 - Combine as produções originais com o resultado da etapa 2 e remova ε - productions.
Problem
Remova a produção nula do seguinte -
S → ASA | aB | b, A → B, B → b | ∈
Solution -
Existem duas variáveis anuláveis - A e B
At first, we will remove B → ε.
Depois de remover B → ε, o conjunto de produção se torna -
S → ASA | aB | b | a, A ε B | b | & épsilon, B → b
Now we will remove A → ε.
Depois de remover A → ε, o conjunto de produção se torna -
S → ASA | aB | b | a | SA | AS | S, A → B | b, B → b
Este é o conjunto de produção final sem transição nula.