LE 1: Inleiding

Question 1

Gegeven is Taal L van alle even binaire getallen waarvan het laatste cijfer een 0 is. Geef een formele specificatie van deze taal.

Answer 1

L={x € {0,1}*: 0 suf x}

Question 2

Geef een definitie van het begrip Formele taal

Answer 2

Een formele taal is een verzameling string over een alfabet

Question 3

_
Gegeven het alfabet ∑={a,b) Bepaal L* en L voor
L = ⏀

Answer 3

a) L=⏀ => L* = ⏀* => ⏀={λ} (check)
_
L = ∑-⏀ = {a,b}*

Question 4

n

Als w een string is: Wat is w

Answer 4

De string n keer herhalen

Question 5

∑ = een alfabet. wat is ∑*

Answer 5

De verzameling string verkregen door 0 of meer symbolen uit het alfabet achter elkaar te zetten.

Question 6

0

als w een string is wat is w ?

Answer 6

λ

Question 7

Wat is ∑+

Answer 7

∑+=∑*={λ}

Question 8

Welke strings maak te met ∑={a,b} en

S-> abS|Sba|a

Answer 8

a, aba, abababa. Dus enkel strings beginnend en eindigend met een a en nooit meer a en b achter elkaar

Question 9

Wat is de Kleene afsluiting

Answer 9

De oneindige verzameling van alle machten van een taal L* = L0 U L1 U L2 …..

Question 10

Wat is de positieve afsluiting

Answer 10

De oneindige verzamelingen van alle machten van een
0
taal - L

L+ = L1 U L2 U …..

Question 11

Wat betekent de “Concatenation” van twee talen. b.v. L1L2

Answer 11

De verzameling strings verkregen door de concatenatie van van elk element uit L1 met elk element uit L2.
L1L2={xy:x € L1, y € L2}

Question 12

Wat is de quadruple of a Grammer

Answer 12

G = (V,T,S,P}
V = Variabels
T = Terminal symbols
S = element V = start variabel
P = finite set production

Question 13

Wat is een Deterministic automata en wat is een non deterministic automata.

Answer 13

Deterministic. Elke verandering uniek te determineren.

Non deterministic. Op elk punt meerdere mogelijkheden om van state te veranderen.

Question 14

Maak 1 tot 5 van paragraaf 1.2

Answer 14

blz 28

Question 15

Maak 6 tot 10 van paragraaf 1.2

Answer 15

blz 28

Question 16

_

Als L een taal is, wat is L* en wat L

Answer 16

L* =de kleene afsluiting.
_
L het complement

Question 17

_
Gegeven het alfabet ∑={a,b) Bepaal L* en L voor
L={lambda}

Answer 17

{λ} bevat alleen de lege string. {λ}* bevat dus ook enkel de lege string. dus {λ}* = {λ}
Het complement bevat alle string uit {a,b} behalve {λ} Dus ∑* - {λ} = ∑+

Question 18

Gegeven het alfabet ∑={a,b) Bepaal L* en L voor

L={a}

Answer 18

zie blz 32

Question 19

Gegeven het alfabet ∑={a,b) Bepaal L* en L voor

L={a}*{b}

Answer 19

zie blz 32