[TA] Doorsnede en Product van 2 DFAs

[Madsen]

Hey de manne,

Ik ben dus aan het leren voor het herexame, en ik ben dus na de theorie aan de oefeningen van TA begonnen. Daar sta ergens in dat ge de doorsnede van 2 DFAs moet tekenen en daar de regex van geven .. allemaal goe en wel maar ik heb blijkbaar toch toen maar wa onzin op men blad gekribbeld en ik herinner me dat ik Doorsnede en Product automaten toen dooreensloeg, maar de mens die mij da toen had uitgelegd is daar nu zelf ook alles al van vergeten

Alsik het goe geleerd heb dan moet ge voor nen product automaat het volgende doen :

- 2 start staten samenvoegen (neem p en s -> (p,s))
- input volgen van de staten apart naar de volgende respectievelijke staat (neem 1 in binaire alfabet) (dit geeft q voor p EN t voor s, en dus kan de een pijl met input 1 getekend worden van (p,s) naar (q,t) etc..)

Maar ik heb niet echt een idee hoe het weer ineenzat voor de doorsnede te nemen .. En in den boek staat het in tegenstelling tot bij product automaten maar bitterweinig info die me kan helpen..

Can someone help me ?

Grts

[Robbe]

Een automaat stelt een taal voor en een taal is een verzameling van strings. You can do the math

[Madsen]

Ik heb overal wa ligge rondkijken en probere en checken enzo en ik heb volges mij de volgende logica bekomen

voor zowel Doorsnede (product) als met Unie moet ge hetzelfde tewerk gaan :

- 2 start staten samenvoegen (neem p en s -> (p,s))
- input volgen van de staten apart naar de volgende respectievelijke staat (neem 1 in binaire alfabet) (dit geeft q voor p EN t voor s, en dus kan de een pijl met input 1 getekend worden van (p,s) naar (q,t) etc..)

en het enige verschil zit em in de accepting states.. bij Doorsnede zijn da de staten waarvan beide staten van beide automaten accepting states moeten zijn om de nieuwe acceptingstate van de (samengevoegde) DFA te kunnen zijn ? en bij de Unie is het voldoende dat er in de samengevoegde set slechts 1 van beide samengevoegde staten een accepting state (in een van de 2 oorspronkelijke DFA) was, om de accepting state in de samengevoegde DFA te kunnen zijn.. ?

Is da correct ?



Madsen.

[Tom]

Voorbehouden op fouten, het is meer dan een jaar geleden dus ik kan het wel eens verkeerd bekijken.

Wat Robbe bedoelt is dat je het van de andere kant moet bekijken, een taal is namelijk een verzameling van strings gevormd met de grammatica, deze worden ook aanvaard door uw automaat. Op deze verzamelingen kan je makkelijker zien wat de unie en doorsnede doen dan bij de automaten.

Unie in talen:
Om de unie te nemen moet je ervoor zorgen dat strings uit beide talen geaccepteerd worden, maar je moet opletten dat je daarmee geen strings introduceert die mogelijk niet in beide talen zitten.

Stel twee reguliere talen L1 en L2:
L1 = {001, 010, 100}
L2 = {000, 111}
L1 unie L2 = {000, 001, 010, 100, 111}

Unie in automaten:
Je zal een soort samengestelde automaat moeten maken die de input van beide automaten aanvaard, dit kan door gebruik te maken van een productautomaat. Als nu een van je originele automaten een string aanvaard dan aanvaard de nieuwe automaat deze ook, omgekeerd is dit niet altijd waar.

Doorsnede in talen:
Om de doorsnede te nemen moet je op zoek gaan naar de strings die in beide talen aanwezig zijn.

Stel twee reguliere talen L1 en L2:
L1 = {000, 001, 011, 111}
L2 = {000, 111}
L1 doorsnede L2 = {000, 111}

Doorsnede in automaten:
Je zal van de twee automaten de pijlen die overeenkomen moeten overnemen. Als nu je nieuwe automaat een string aanvaard dan aanvaarden de twee originele automaten deze ook, omgekeerd is dit niet altijd waar.

[Robbe]

Ik heb overal wa ligge rondkijken en probere en checken enzo en ik heb volges mij de volgende logica bekomen

...

Is da correct ?

Lijkt mij juist, maar is uw doorsnede dan niet gewoon een product van 2 automaten?

Je doet dat product/doorsnede/unie toch met een matrix he?

[Madsen]

Ik heb overal wa ligge rondkijken en probere en checken enzo en ik heb volges mij de volgende logica bekomen

...

Is da correct ?

Lijkt mij juist, maar is uw doorsnede dan niet gewoon een product van 2 automaten?

Ja awel robbe da dacht ik dus ook, maar nu zegt tom da da me de Unie is.. maar in den boek (138) staat er een voorbeeld van een product en da is op de wijze van de doorsnede gedaan ..

[Pieter Belmans]

Een string zit in de doorsnede van 2 talen als hij door beide automaten die die talen voorstellen aanvaard wordt. Redelijk obvious, want dan zit hij zowel in de ene als de andere taal .

[Madsen]

Een string zit in de doorsnede van 2 talen als hij door beide automaten die die talen voorstellen aanvaard wordt. Redelijk obvious, want dan zit hij zowel in de ene als de andere taal .

oki en als ze dan het product van 2 automaten vragen is da dan de doorsnede of de unie ? voor de rest heb ik het eindelijk door :p

[Pieter Belmans]

Het hangt er allemaal van af hoe ge uw eindstaten definieert. Is een eindstaat in de productautomaat opgebouwd uit minstens 1 of 2 eindstaten van de automaten in uw constructie? 1 is unie (want als er 1 aanvaardt zit er immers al in), 2 is doorsnede (zie boven). Correct me if I'm wrong, het is alweer even geleden .