LE 2 Finite automata

Question 1

Wat is een dfa

Answer 1

Deterministic finite adapter

Question 2

Geef een definitie van een dfa

Answer 2

Een dfa wordt gedefinieerd door een quintuple:
M=(Q,∑,δ,q0,F)
Q= finit set of internal states
∑= finit set of input symbols, input alfabet
δ=Qx ∑->Q total function called transition function
q0 ∈ Q is de initial state
F ⊆ Q is een set final states

Question 3

Wat legt de uitgebreide overgangsfunctie vast

Answer 3

Wat het resultaat is van het toepassen van een aantal overgangen achter elkaar. Dus bijvoorbeeld van een hele string

Question 4

Geef de recursieve definitie

Answer 4

δ(q,wa) = δ(δ(q,w),a)

Question 5

Wat is een trap state

Answer 5

Dit is een toestand waar een eindige automaat niet meer uitkomt

Question 6

Wat houdt het in dat een dia “ totaal” is.

Answer 6

voor iedere toestand en invoersymbool is er precies 1 pijl naar een toestand met als invoersymbool als label van de pijl

Question 7

Wat houdt het deterministische in van de DFA

Answer 7

Voor iedere input string is er maar 1 pad door de automaat.

Question 8

Hoe bepalen we dat een language “Regular” is

Answer 8

Door een automaat te construeren die de taal accepteert.

Question 9

Maak opgave 2.13

Answer 9

blz 39

Question 10

Geef de definitie van de overgangsfunctie voor een NFA

Answer 10

Q

δ:Qx(∑ U {λ}) -> 2

Question 11

Oefen NFA met opgave 2.16

Answer 11

blz 40

Question 12

Als M=(Q,∑,δ,q0,F) en M=(Q,∑,δ,q0,Q-F)
___ ^
Dan is L(M) = L(M)

Leg uit

Answer 12

zie antwoord 2.5 blz 47