Reguliere taal: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
beslisbare problemen komen in dit lemma niet voor dus ik denk dat het hele hoofdstuk bedoeld is |
+beslissingsproblemen |
||
Regel 29:
* het omgekeerde (of spiegelbeeld) <math>L^R</math> van ''<math>L</math>'',
* HALF(''L''), de verzameling van strings die bestaan uit de eerste helft van de strings in ''<math>L</math>''
== Beslisbare eigenschappen ==
Een van de redenen dat reguliere talen vaak gebruikt worden, is dat veel [[Beslissingsprobleem|beslissingsproblemen]] met betrekking tot reguliere talen [[Berekenbaarheid|beslisbaar]] zijn. Ten eerste is het beslisbaar of een willekeurig woord tot de taal behoort.
Of een reguliere taal <math>L</math> leeg is (<math>L = \varnothing</math>) 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 <math>L_1</math> en <math>L_2</math>, beslis of <math>L_1 \subseteq L_2</math> (dit geldt als <math>L_1 - L_2</math> leeg is)
* Equivalentie: gegeven reguliere talen <math>L_1</math> en <math>L_2</math>, beslis of <math>L_1 = L_2</math> (dit geldt als <math>L_1 \subseteq L_2</math> en <math>L_2 \subseteq L_1</math>)
* Universaliteit: gegeven een reguliere taal <math>L</math>, beslis of <math>L=\Sigma^*</math> (dit geldt als het complement van <math>L</math> leeg is)
== Beslissen of een taal regulier is ==
Regel 34 ⟶ 42:
== Referenties ==
* {{en}} {{Citeer boek|author = John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman|year=2007|title=Introduction to Automata Theory, Languages and Computation, Third Edition|publisher = Addison-Wesley}}
* {{en}} {{Citeer boek|author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | ISBN = 0-534-94728-X}} Chapter 1: Regular Languages
| |||