O que é regularidade?
-
19-09-2019 - |
Pergunta
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?
Solução
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 .
Outras dicas
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 n b n 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) n é 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".
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 n b n (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.
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
expressão regular não são realmente regular, o nome é etimológica.