Che cosa è la regolarità?

Question

Questo è più di una domanda di informatica di uno di programmazione, ma immagino che questo è il posto migliore tra tutti i siti correlati a chiedere questo.

Quando ho scoperto espressioni regolari e guardato il termine ho pensato che questa proprietà di "regolarità" si riferisce al fatto che il linguaggio dell'espressione ha un modello strutturale definibile. Tuttavia, nella lettura sull'argomento e la teoria alla base di questo ho imparato che ci sono tipi di linguaggi che non sono regolari, e ancora dal modo in cui vengono definiti è chiaro che un modello può essere abbinato a loro. Un tale linguaggio è (a ^ n) (b ^ n). Chiaramente questo è un modello, ma questo non è un linguaggio regolare. Così ora sto sinistra chiedo che cosa si tratta linguaggi regolari che li rende regolare, e questo non la lingua?

Answer 1

L'etimologia del nome deriva dal 1950 il lavoro di Kleene descrivendo insiemi regolari usando la sua notazione matematica creato allo scopo. Vedere questo .

Answer 2

Intuitivamente spiegare l'informatica è ... difficile. Darò un colpo, ma di tenere presente che alcuni di questo sta per essere "abbastanza vicino", ma non teoricamente rigoroso.

Un linguaggio regolare è uno che può essere deciso da una macchina che è equivalente ad un calcolo automi a stati finiti (DFAE / NDFA). Un automi finiti può essere pensato come una macchina che opera unicamente in stati, nessun deposito. Così si può vedere che un ⁿ b ⁿ non può essere regolare in quanto richiede una macchina che può contare il numero di A e B di (e quindi deve avere infinita * capacità di stoccaggio) al fine di confrontarli.

Per fare un confronto, (abc) ⁿ regolare, perché il numero di ripetizioni è irrilevante.

Per una più rigorosa (e corrispondentemente vista più densa) Controllare il wikipedia articolo e pagine collegate .

_{* L'infinito non importa qui, ma ne parla per completezza. Potrebbe essere più facile pensare ad esso come storage "per fortuna, sempre appena sufficiente".}

Answer 3

Forse alle voci di Wikipedia linguaggi regolari può spiegare meglio di noi. Tuttavia, ho deciso di dargli un colpo.

Da un punto di vista teorico, un linguaggio regolare (insieme di stringhe) è uno che può essere generato utilizzando un stati finiti automa . Dal punto di vista del programmatore, questo equivale a dire che può essere generato utilizzando espressioni regolari . Così, tutte le lingue finite (insiemi di stringhe) sono regolari, ma ci sono alcune lingue infiniti, come ad esempio un ⁿ b ⁿ (il linguaggio di tutte le stringhe di na di seguito da n per b) che non possono essere riconosciuti con un FSA o espressioni regolari. Ci sono più potenti dispositivi di calcolo (come i computer moderni, che vengono modellati utilizzando macchine di Turing ) che possono riconoscere quelle lingue.

La ragione per le espressioni regolari sono usati tanto in programmazione per la ricerca della stringa è che possono riconoscere la grande maggioranza delle stringhe che sono importanti per noi programmatori, e allo stesso tempo può essere implementata per la ricerca molto rapidamente utilizzando automi a stati finiti.

Answer 4

La parola regular in regular expression si riferisce al concetto matematico di regolare, non il concetto inglese. Proprio come come la parola prime in matematica avere poca correlazione con primo di manzo.

E 'ereditato da CS (che è un ramo della matematica) per riferirsi ad un concetto più specifico: http : //en.wikipedia.org/wiki/Regular_language

Answer 5

espressioni regolari non sono realmente regolare, il nome è etimologico.