o principal diferença entre a expressão regular e a 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 a gramática regular e a gramática livre de contexto. Qualquer linguagem que pode ser descrita por uma expressão regular é uma linguagem 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.

Expressão regular, gramática livre de contexto

O que é expressão regular

A gramática regular gera linguagens regulares. Esta gramática tem um único não terminal no lado esquerdo e um lado direito consistindo em um único terminal ou único terminal seguido por um único não terminal. Ele pode ter uma regra de produção da seguinte maneira.

X -> a ou X -> a Y

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

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

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

1. Os símbolos terminais, símbolo nulo e 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 + denota o fechamento de um símbolo excluindo o símbolo vazio.

O que é Gramática Livre de Contexto

Na teoria da linguagem formal, Context Free Language (CFL) é uma linguagem gerada pela Gramática Livre de Contexto. Quatro parâmetros definem a 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 terminais

S: Símbolo de início

P: Regra de Produção

A Gramática Livre de Contexto tem o seguinte formato para 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.

Pois a geração de uma linguagem que gera um número igual de a e b está no formato de um b . A gramática livre de contexto é a seguinte.

G = {(S, A), (a, b), (S -> aAb, A -> aAb | ϵ)}

Considerando o símbolo inicial,

S -> a A b

Ao aplicar A -> aAb

→ a a A b b

Ao aplicar 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

→ a ³ b ³

Ao considerar a saída, o número de a's é igual ao número de b's. Tem o a b Formato.

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

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

Definição

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

Uso

As expressões regulares ajudam a representar certos conjuntos de strings de uma forma algébrica. Isso ajuda a representar linguagens 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 um meio flexível e conciso de combinar sequências de texto. Ele define todas as strings na linguagem 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 a expressão regular e a 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, disponível aqui.2. “Introdução à gramática livre de contexto.” Www.tutorialspoint.com, Tutorials Point, 8 de janeiro de 2018, disponível aqui.

Cortesia de imagem:

1. “Toolbaricon RegEx” de M0tty - Trabalho próprio (CC BY-SA 4.0) via Commons Wikimedia