Samenvatting: Introduction To The Theory Of Computation | 9781285401065 | Michael Sipser

Lees hier de samenvatting en de meest belangrijke oefenvragen van Introduction to the Theory of Computation | 9781285401065 | Michael Sipser

• 0 Introduction

• 0.1 Strings en operaties daar op

  Dit is een preview. Er zijn 1 andere flashcards beschikbaar voor hoofdstuk 0.1
  Laat hier meer flashcards zien

• Wat is een alfabet? En met welke symbolen representeren we doorgaans een alfabet?

  Een alfabet is iedere niet-lege (doch eindigende) verzameling met symbolen. We representeren een alfabet doorgaans met de griekse hoofdletters sigma en tau.

• Wat is het lege woord, en hoe geven we deze aan? Wat is de lengte?

  Het lege woord is de string met lengte 0. We geven deze weer met kleine epsilon.

• 1 Regular Languages

• Wat is een reguliere taal?

  Een taal L is regulier desda er een DFA M bestaat waarvoor geldt L = L(M). Informeel kan je zeggen: een taal is is een reguliere taal als er een eindigend automaat bestaat dat deze herkend.

• Noem 3 eigenschappen van regulieren talen.

  1. De klasse van reguliere talen is gesloten onder complement.
  2. De klasse van reguliere talen is gesloten onder vereniging.
  3. De klasse van reguliere talen is gesloten onder doorsnede.

• 1.1 Finite automata

  Dit is een preview. Er zijn 8 andere flashcards beschikbaar voor hoofdstuk 1.1
  Laat hier meer flashcards zien

• Wat is de taal van machine M?

  De taal van machine M is de set van alle strings die M accepteerd.

• Wat is een taal die herkend wordt door een DFA, en hoe wordt die gedefinieerd?

  Een taal A die herkend wordt door een DFA M, is gedefinieerd door: A = { w | M accepts w }.

• Stel we hebben alfabet Sigma dat uit de standaard 26 letters bestaat. Taal A = {good, bad}. Taal B = {boy, girl}. Laat de resultaten zien als we de volgende regular operations: union, concatenation en star uitvoeren op de talen.

  Union = {good, bad, boy, girl}

  Concatenation = { goodboy, goodgirl, badboy, badgirl}{

  Star (enkel op 1 taal toepasbaar) = {epsilon, good, bad, goodgood, goodbad, badgood, badbad, ......}.

• Wat is een NFA? En wat zijn de drie verschillen met een DFA?

  Een NFA is een niet-deterministische eindige automaat. Dit zijn de verschillen:

  1. Meerdere transities voor een symbol mogelijk vanuit een toestand.
  2. Er bestaat de mogelijkheid dat er vanuit een toestand geen transitie voor een symbol is gedefinieerd.
  3. -transities: niets lezen en toch naar een andere toestand.

• In welk opzicht verschilt de definitie van een NFA met de DFA?  

  Ze zijn beide een 5-tuple, maar de definitie van de transitie functie is anders.

  DFA:

  NFA:  (laatste Q moet \Rho{Q} zijn.)

• Wanneer zijn automaten equivalent?

  Automaten M1 en M2 zijn equivalent desda L(M1) = L(M2)