De reguliere talen vormen een klasse van formele talen. Reguliere talen hebben een relatief eenvoudige structuur, waardoor ze zeer geschikt zijn om door computerprogramma's verwerkt te worden. Daarom hebben ze vele toepassingen in de informatica, onder andere in tekstbewerkingsprogramma's (reguliere expressies), in de compilerbouw (in het bijzonder bij de lexicale analyse) en bij modelverificatie.

Definitie

bewerken

Een alfabet   is een verzameling van letters. De verzameling van reguliere talen over het alfabet   is recursief gedefinieerd:

  • De lege taal   is een reguliere taal.
  • De taal die slechts uit de lege string bestaat,  , is een reguliere taal.
  • Voor alle   is de singletontaal   een reguliere taal.
  • Als   en   reguliere talen zijn, dan zijn ook   (vereniging),   (concatenatie) en   (Kleene-ster) reguliere talen.
  • Geen andere talen over   zijn regulier.

Alternatief kan een reguliere taal ook gedefinieerd worden als een formele taal die een van de volgende equivalente eigenschappen vervult:

Alle eindige talen zijn regulier. Andere voorbeelden zijn de taal die bestaat uit alle strings over het alfabet   met een even aantal  's, of de taal van de vorm: een aantal  's gevolgd door een aantal  's.

Afsluiteigenschappen

bewerken

De reguliere talen zijn gesloten onder de volgende bewerkingen, dit betekent: als   en   reguliere talen zijn, dan zijn de volgende talen ook regulier:

  • de booleaanse operaties: de vereniging  , doorsnede  , en het complement   van  , en daardoor ook het verschil  ,
  • de reguliere operaties: concatenatie   en Kleene-ster   van   en  ,
  • het beeld   van   onder een homomorfisme,
  • het omgekeerde (of spiegelbeeld)   van  ,
  •  , de verzameling van strings die bestaan uit de eerste helft van de strings in  .

Beslisbare eigenschappen

bewerken

Een van de redenen dat reguliere talen vaak gebruikt worden, is dat veel beslissingsproblemen met betrekking tot reguliere talen beslisbaar zijn. Ten eerste is het beslisbaar of een willekeurig woord tot de taal behoort.

Of een reguliere taal   leeg is ( ) kan bepaald worden door vast te stellen of er in de DFA van de taal minstens een pad van een begin- naar een eindtoestand is; als dat niet het geval is, is de taal leeg. Dit kan met een padzoekalgoritme worden bepaald. Aangezien de reguliere talen afgesloten zijn onder booleanse operaties (zie boven), volgt hier ook uit dat de volgende beslissingsproblemen beslisbaar zijn:

  • Deelverzameling: gegeven reguliere talen   en  , beslis of   (dit geldt als   leeg is)
  • Equivalentie: gegeven reguliere talen   en  , beslis of   (dit geldt als   en  )
  • Universaliteit: gegeven een reguliere taal  , beslis of   (dit geldt als het complement van   leeg is)

Beslissen of een taal regulier is

bewerken

In de Chomskyhiërarchie kan men zien dat elke reguliere taal contextvrij is. Het omgekeerde is echter niet het geval: bijvoorbeeld de taal die bestaat uit alle strings met hetzelfde aantal  's en  's is contextvrij, maar niet regulier. Om te bewijzen dat een taal niet regulier is gebruikt men de stelling van Myhill-Nerode of de pompstelling.

Referenties

bewerken
  • (en) John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007). Introduction to Automata Theory, Languages and Computation, Third Edition. Addison-Wesley.
  • (en) Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 1: Regular Languages