Diferença entre a expressão regular e a gramática livre de contexto - Diferença Entre

Diferença entre a expressão regular e a gramática livre de contexto

o principal diferença entre expressão regular e gramática livre de contexto é que o expressões regulares ajudam a descrever todas as strings de uma linguagem regular enquanto a gramática livre de contexto ajuda a definir todas as strings possíveis de uma linguagem livre de contexto.

Gramática denota regras sintáticas para conversação em linguagens naturais. A Ciência da Computação usa a teoria das linguagens formais em grande medida. No ano de 1956, Noam Chomsky deu um modelo matemático de gramática para escrever linguagens de computador. Quando é possível derivar um conjunto de todas as strings de uma gramática, diz-se que a linguagem é gerada a partir dessa gramática. Dois tipos de gramática são gramática livre e gramática livre de contexto. Qualquer idioma que possa ser descrito por uma expressão regular é um idioma regular. A gramática livre de contexto é uma generalização da expressão regular. É possível usar expressões regulares para escrever linguagens regulares e gramática livre de contexto para escrever gramática livre de contexto.

Principais áreas cobertas

1. O que é expressão regular
- Definição, Exemplos
2. O que é gramática livre de contexto
- Definição, Exemplos
3. Relação entre Expressão Regular e Gramática Livre de Contexto
- Esboço da Associação
4. Diferença entre Expressão Regular e Gramática Livre de Contexto
- Comparação de diferenças-chave

Termos chave

Expressão Regular, Gramática Livre de Contexto


O que é expressão regular?

A gramática regular gera idiomas regulares. Essa gramática possui um único terminal não-terminal no lado esquerdo e um lado direito que consiste em um único terminal ou terminal único seguido por um único terminal não-terminal. Pode ter uma regra de produção como segue.

X -> a ou X -> a Y

Onde X, Y ϵ N (não terminal) e ϵ T (terminal)

Expressões regulares ajudam a escrever gramática regular para descrever idiomas regulares.


Uma expressão regular representa um certo conjunto de cadeias de caracteres de forma algébrica. Algumas regras importantes a serem seguidas ao escrever uma expressão regular são as seguintes.

  1. Os símbolos do terminal, o símbolo nulo e o símbolo vazio são expressões regulares.
  2. A união de duas expressões regulares é uma expressão regular.
  3. A concatenação de duas expressões regulares é uma expressão regular.
  4. Iteração ou encerramento é uma expressão regular.

A expressão regular para o conjunto {0,1,2} é a seguinte.

R = 0 + 1 + 2

O conjunto {abb, a, b, bba} pode ser representado pela seguinte expressão regular.

R = abb + a + b + bba

Considere o conjunto, {ϵ, 0, 00, 000,…}

O ϵ é a string vazia. A expressão regular é R = 0 *. Isso representa o fechamento do símbolo, incluindo o símbolo vazio.

No conjunto {1, 11, 111, 1111,… ..}

A expressão regular é R = 1 +.  Este + indica o fechamento de um símbolo excluindo o símbolo vazio.

O que é gramática livre de contexto

Na teoria da linguagem formal, o Context Free Language (CFL) é uma linguagem gerada pela Gramática Livre de Contexto. Quatro parâmetros definem gramática livre de contexto (G).

G = {V, ∑, S, P}

V: Conjunto de símbolos variáveis ​​ou não terminais.

∑: Conjunto de símbolos de terminal

S: símbolo inicial

P: Regra de produção

A gramática livre do contexto tem o seguinte formato para a regra de produção.

A -> a onde a = {V, ∑} * e A ϵ V

Um exemplo de gramática livre de contexto é o seguinte. Cada produção consiste em um símbolo não terminal e uma expressão regular.

Para gerar uma linguagem que gera um número igual de a e b está no formato de umnbn. A gramática livre do contexto é a seguinte.

G = ϵ)

Considerando o símbolo inicial,

S -> a A b

Aplicando A -> aAb

→ a a A b b

Aplicando A -> aAb novamente,

→ a a a A b b b

Aplicando A -> ϵ (Este símbolo denota uma string vazia)

→ a a a b b b

→ um 3 b 3

Ao considerar a saída, o número de a é igual ao número de bs. Tem o umn bn Formato.

Relação entre Expressão Regular e Gramática Livre de Contexto

  • A gramática livre de contexto é uma generalização de expressões regulares.

Diferença entre a expressão regular e a gramática livre de contexto

Definição

Uma expressão regular é um conceito na teoria formal da linguagem, que é uma sequência de caracteres que define um padrão de pesquisa. Contexto A gramática livre é um tipo de gramática formal na teoria da linguagem formal, que é um conjunto de regras de produção que descrevem todas as cadeias possíveis em uma determinada linguagem formal.

Uso

Expressões regulares ajudam a representar certos conjuntos de string de forma algébrica. Isso ajuda a representar idiomas regulares. A gramática livre de contexto ajuda a definir todas as strings possíveis de uma linguagem livre de contexto.

Conclusão

Uma expressão regular é um método para correspondência de padrões. É um método flexível de fornecer meios flexíveis e concisos para combinar strings de texto. Ele define todas as strings no idioma regular. Por outro lado, a gramática livre de contexto permite definir todas as strings pertencentes a uma linguagem livre de contexto. A diferença entre expressão regular e gramática livre de contexto é que as expressões regulares ajudam a descrever todas as strings de uma linguagem regular enquanto a gramática livre de contexto ajuda a definir todas as strings possíveis de uma linguagem livre de contexto.

Referência:

1. “Expressões Regulares”. Www.tutorialspoint.com, Tutorials Point, 8 de janeiro de 2018,