Diferença entre expressão regular e gramática em autômatos

Eu sou novo em autômatos e recebi uma breve introdução às expressões regulares apenas ontem. Eu li as várias regras para definir uma expressão regular. Mas não sou capaz de diferenciar expressões regulares e gramática de um idioma (não aprendi a gramática para expressões regulares).

Entendo que a gramática nos ajuda a gerar as seqüências de caracteres válidas em um idioma, mas é isso que as regras para definir expressões regulares. Então, onde está a diferença? Perguntei ao meu professor e ele disse que regex são as seqüências mais básicas de um idioma e gramática é o conjunto de regras para qualquer idioma, que são de ordem superior à regex. Alguém pode fornecer informações mais detalhadas?

Expressões regulares, gramáticas regulares e autômatos finitos são simplesmente três formalismos diferentes para a mesma coisa. Existem algoritmos para converter de um para outro.

A razão básica de termos todos os três é que eles foram criados independentemente, com o primeiro conjunto de equivalências (também existem vários outros formalismos) comprovado por Kleene (esse resultado, ou parte dele, é chamado de Teorema de Kleene).

Portanto, nesse contexto, dependendo de como você deseja executar os modelos, todos eles reconhecem ou geram seqüências de caracteres de uma linguagem regular e, matematicamente, não há, nesse sentido, nenhuma diferença.

É claro que às vezes um modelo é mais fácil de usar do que outro para uma tarefa específica, devido aos detalhes do formalismo. Além disso, a maneira como eles trabalham na cabeça de um ser humano é muitas vezes um pouco diferente, os autômatos finitos "parecem" computadores, as expressões regulares "parecem" como se você estivesse construindo uma cadeia de caracteres com substrings menores e as gramáticas regulares "parecem" uma gramática mais tradicional derivação ou classificação de uma sentença em um idioma (sem surpresa quando você olha para o histórico).

Então, para comparar os dois, vamos defini-los:

Expressões regulares

Portanto, expressões regulares são definidas recursivamente da seguinte maneira:

1. é uma expressão regular$\emptyset$
2. $\varepsilon$ é uma expressão regular
3. $a$ é uma expressão regular para todo$a \in \Sigma$
4. se e são expressões regulares, $A$$B$
   • $A\cdot B$ is a regular expression (concatentation)
   • $A \mid B$ is a regular expression (alternation)
   • $A^{\ast}$ is a regular expression (Kleene star)

Along with some semantics (i.e. how we interpret the operators to get a string), we get a way of generating strings from a regular language.

Regular Grammars

Regular grammars consist of a four tuple $(N,\Sigma, P, S \in N)$ where $N$ is the set of non-terminals, $\Sigma$ is the set of terminals, $S$ is the start non-terminal and $P$ is the set of productions which tell us how to change the start symbol, step by step, into a string in $\Sigma^{\ast}$. $P$ can have its productions drawn from one of two types (not both though):

Right Linear Grammars

For non-terminals $B$, $C$, terminal $a$ and the empty string $\varepsilon$, all rules are of the form:

1. $B \rightarrow a$
2. $B \rightarrow aC$
3. $B \rightarrow \varepsilon$

Left Linear Grammars

Left linear grammars are the same, but rule #2 is $B \rightarrow Ca$.

Things to Ponder

So looking at these definitions and playing with them, we can see that regular expressions look like matching rules, or ways of dealing with strings a bit at a time.

Grammars seem to "label" sections of the string, and group labels under new labels to validate the string (i.e. if we can get from $S$ to the string, or vice versa, we're happy).

However these are really doing the same fundamental thing, and how you view the metaphor of their function is really up to you.