Regular Languages - Finite automata

5 belangrijke vragen over Regular Languages - Finite automata

Wat is een regular expression?

Dit zijn uitdrukkingen/formules waarmee reguliere talen kunnen worden opgeschreven.

Wat is een GNFA, en wat is het verschil met een NFA?

Een GNFA is een Gegeneraliseerde Niet-deterministische Eindige Automaat. Er is precies één accepterende toestand Qa, geen transities naar Qs, geen transities vanuit Qa.

Welke 4 stappen zijn er om een NFA m om te zetten naar een GNFA m'?

  1. Creëer, indien nodig, een nieuwe starttoestand zonder inkomende transities.
  2. Creëer, indien nodig, een unieke accepterende toestand zonder uitgaande transities.
  3. Voeg parallele transities samen.
  4. Voeg, indien nodig, transities met label 0 toe.
  • Hogere cijfers + sneller leren
  • Niets twee keer studeren
  • 100% zeker alles onthouden
Ontdek Study Smart

Wat is het pigeonhole principe?

Het principe dat als je bijvoorbeeld 9 opbergvakjes hebt, en je meer dan 9 dingen moet opbergen, er in ieder geval 1 hokje 2 dingetjes zal hebben.

Hoe luidt de pompstelling?

Zij L een oneindige, reguliere taal, dan:
  1. bestaat er een p > 0, de pomplengte van L, en
  2. voor ieder woord w in L, waarvoor geldt dat de lengte groter of gelijk is aan w.
  3. bestaat er een opsplitsing w = xyz, met |xy| <= p, en |y| > 0, zodat
  4. Voor alle i >= 0 geldt xy^iz zit in L.

De vragen op deze pagina komen uit de samenvatting van het volgende studiemateriaal:

  • Een unieke studie- en oefentool
  • Nooit meer iets twee keer studeren
  • Haal de cijfers waar je op hoopt
  • 100% zeker alles onthouden
Onthoud sneller, leer beter. Wetenschappelijk bewezen.
Trustpilot-logo