O que é regularidade?

Question

Esta é mais uma questão de ciência da computação do que uma programação, mas eu figura que este é o melhor lugar de todos os sites relacionados para perguntar isso.

Quando descobri Expressões Regulares e olhou para o termo eu assumi que esta propriedade da "regularidade" refere-se ao fato de que a linguagem da expressão tem um padrão estrutural definível. No entanto, ao ler sobre o assunto e a teoria por trás disso eu aprendi que existem tipos de linguagens que não são regulares, e ainda da forma como eles são definidos é claro que um padrão pode ser combinado com eles. Uma tal linguagem é (a ^ n) (b ^ n). Claramente este é um padrão, e no entanto esta não é uma linguagem regular. Então agora eu estou deixado querer saber o que é sobre linguagens regulares que os torna regular, e isso não idioma?

Answer 1

A etimologia do nome vem de 1950 de Kleene trabalho descrevendo conjuntos regulares usando sua notação matemática criada para o efeito. Consulte este .

Answer 2

Intuitivamente explicando ciência da computação é ... complicado. Vou dar-lhe um tiro, mas tenha em mente que alguns dos isso vai ser "suficientemente próximo", mas não teoricamente rigorosa.

A linguagem regular é aquele que pode ser decidida por uma máquina que é computacional equivalente a um autômatos finitos (DFA / DNPA). A autômatos finitos pode ser pensado como uma máquina que opera exclusivamente em estados, nenhum armazenamento. Assim você pode ver que a ⁿ b ⁿ não pode ser regular, pois requer uma máquina que pode contar o número de A e b (e, portanto, deve ter infinita * capacidade de armazenamento) a fim de compará-los.

Para comparação, (abc) ⁿ é regular, porque o número de repetições é irrelevante.

Para uma mais rigorosa (e correspondentemente vista mais denso) verificar o wikipedia artigo e páginas linkadas .

_{* O infinito não importa aqui, mas eu mencioná-lo para ser completo. Pode ser mais fácil pensar nisso como armazenamento "felizmente, sempre apenas o suficiente".}

Answer 3

Talvez o artigo da Wikipedia sobre linguagens regulares pode explicar melhor do que nós. No entanto, vou dar-lhe um tiro.

Do ponto de vista teórico, uma linguagem regular (conjunto de cordas) é aquele que pode ser gerado usando um finito autômato. Em termos programador, este é equivalente a dizer que pode ser gerado usando expressões regulares . Assim, todas as línguas finitos (conjuntos de cordas) são regulares, mas existem algumas línguas infinitas, como um ⁿ b ⁿ (a linguagem de todas as cadeias de nd de seguido por n de b) que não pode ser reconhecido usando um FSA ou expressões regulares. Há mais poderosos dispositivos computacionais (como computadores modernos, que são modeladas utilizando Turing Machines ) que pode reconhecer esses idiomas.

A razão expressões regulares são usadas tanto na programação para a busca das cordas é que eles podem reconhecer a grande maioria das cordas que são importantes para nós programadores, e ao mesmo tempo pode ser implementado para procurar muito rapidamente usando finito autômatos estado.

Answer 4

A palavra regular em regular expression refere-se ao conceito matemático de, não o conceito regular de Inglês. Assim como como a palavra prime em matemática têm pouca relação com nobre carne.

É herdada por CS (que é um ramo da matemática) para se referir a um conceito mais específico: http : //en.wikipedia.org/wiki/Regular_language

Answer 5

expressão regular não são realmente regular, o nome é etimológica.