CFG significa gramática livre de contexto. É uma gramática formal usada para gerar todos os padrões possíveis de strings em uma determinada linguagem formal. A gramática livre de contexto G pode ser definida por quatro tuplas como:
G = (V, T, P, S)
Onde,
G é a gramática, que consiste em um conjunto de regras de produção. É usado para gerar a string de um idioma.
T é o conjunto final de um símbolo terminal. É indicado por letras minúsculas.
EM é o conjunto final de um símbolo não terminal. É indicado por letras maiúsculas.
P é um conjunto de regras de produção, que é usado para substituir símbolos não terminais (no lado esquerdo da produção) em uma string por outros símbolos terminais ou não terminais (no lado direito da produção).
concatenação de string java
S é o símbolo inicial usado para derivar a string. Podemos derivar a string substituindo repetidamente um não-terminal pelo lado direito da produção até que todos os não-terminais tenham sido substituídos por símbolos terminais.
Exemplo 1:
Construa o CFG para a linguagem que possui qualquer número de a no conjunto ∑= {a}.
Solução:
Como sabemos, a expressão regular para a linguagem acima é
r.e. = a*
A regra de produção para a expressão regular é a seguinte:
S → aS rule 1 S → ε rule 2
Agora, se quisermos derivar uma string 'aaaaaa', podemos começar com símbolos iniciais.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Lá. = a* pode gerar um conjunto de strings {ε, a, aa, aaa,.....}. Podemos ter uma string nula porque S é um símbolo inicial e a regra 2 fornece S → ε.
Exemplo 2:
Construa um CFG para a expressão regular (0+1)*
Solução:
boto3
O CFG pode ser dado por,
Production rule (P): S → 0S | 1S S → ε
As regras estão na combinação de 0 e 1 com o símbolo inicial. Já que (0+1)* indica {ε, 0, 1, 01, 10, 00, 11, ....}. Neste conjunto, ε é uma string, então na regra podemos definir a regra S → ε.
Exemplo 3:
Construa um GFC para uma linguagem L = onde w € (a, b)*.
Solução:
A string que pode ser gerada para um determinado idioma é {aacaa, bcb, abcba, bacab, abbcbba, ....}
A gramática poderia ser:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Agora, se quisermos derivar uma string 'abbcbba', podemos começar com símbolos iniciais.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Assim, qualquer string desse tipo pode ser derivada das regras de produção fornecidas.
quem inventou a escola
Exemplo 4:
Construa um CFG para a linguagem L = anb2nonde n>=1.
Solução:
A string que pode ser gerada para um determinado idioma é {abb, aabbbb, aaabbbbbb....}.
A gramática poderia ser:
S → aSbb | abb
Agora, se quisermos derivar uma string 'aabbbb', podemos começar com símbolos iniciais.
S → aSbb S → aabbbb