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

12

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?

Charu Bansal
fonte

Respostas:

22

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
  2. ε é uma expressão regular
  3. a é uma expressão regular para todoaΣ
  4. se e são expressões regulares, AB
    • AB is a regular expression (concatentation)
    • AB is a regular expression (alternation)
    • A 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,Σ,P,SN) where N is the set of non-terminals, Σ 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 Σ. 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 ε, all rules are of the form:

  1. Ba
  2. BaC
  3. Bε

Left Linear Grammars

Left linear grammars are the same, but rule #2 is BCa.

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.

Luke Mathieson
fonte
I'd put more emphasis on the fact that grammars generate strings in the language, while regular expressions (as you said) are more of a matching pattern that matches (or, "test") every string in the language.
Ran G.
@RanG., that is indeed the usual way to think of it, but you can flip both around; bottom up parsing tests a string against a grammar, and you can use a regular expression as a compact description of a language (though this is probably less common).
Luke Mathieson
@simpleBob N is the set of nonterminals, S is the starting nonterminal. What would R be?
Luke Mathieson
@LukeMathieson My mistake, I read the paragraph and thought it was a typo with N because of the order where R was defined. Now that I have read the formal definition elsewhere, it seems that the typo was that R should be P (I think) (Second line in the first Regular Grammars paragraph)
Daniel
@simpleBob, Ah yes, that's definitely a typo. Thanks!
Luke Mathieson