Toplista
- betöltés...
Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Adjuk meg véges, teljesen definiált determinisztikus automatákkal?
Márk462
kérdése
384
Valaki tudna segíteni ennek a feladatnak a megoldásában?
https://kepkuldes.com/image/e3PpC3
Főként itt a (|w|a + 2*|w|b) >= 5 nem világos. Ez azt jelenti, hogy az automata olyan szavakat fogad el ahol a B-k darabszáma kétszer több mint az A-k darabszáma és az összegük >= 5? Szóval olyan szavakat ( ha csak ezt a részt nézzük) ahol pl 2 db A 4 db B, 3 db A 6 db B stb...?
https://kepkuldes.com/image/e3PpC3
Főként itt a (|w|a + 2*|w|b) >= 5 nem világos. Ez azt jelenti, hogy az automata olyan szavakat fogad el ahol a B-k darabszáma kétszer több mint az A-k darabszáma és az összegük >= 5? Szóval olyan szavakat ( ha csak ezt a részt nézzük) ahol pl 2 db A 4 db B, 3 db A 6 db B stb...?
Jelenleg 1 felhasználó nézi ezt a kérdést.
Matematik, automata
Matematik, automata
0
Felsőoktatás / Matematika
Válaszok
1
bongolo
{ 
}
megoldása
Szerintem azt jelenti, hogy az a-k számához hozzáadod a b-k számának dupláját, és az legalább 5.
Persze ez akkor igaz, ha a `|w|_a` jelölés azt jelenti, hogy a `w` szóban lévő `a` szimbólumok száma. Bizonyára azt jelenti...
Szóval mondjuk `aaaaa` egy jó szó, `aaba` szintén, `b baa` szintén, stb.
Csinálj két automatát, az egyik számolja ezt az összeget, a másik meg azt nézze, hogy hárommal nem osztható darab c van-e. Aztán ennek a két automatának kell venni a direkt szorzatát.
Az első automata ilyesmi lehet:
`q_0` a kiinduló állapot, `q_5` az elfogadó.
Hint: A `q_n` állapot (`n=0,1,2,3,4`) azt jelenti, hogy a `|w|_a + 2*|w|_b` összeg éppen `n`. A `q_5` meg azt jelenti, hogy `≥ 5`.
`δ(q_0,a)=q_1, δ(q_1,a)=q_2, δ(q_2,a)=q_3,δ(q_3,a)=q_4,δ(q_4,a)=q_5,δ(q_5,a)=q_5`
`δ(q_0,b)=q_2, δ(q_1,b)=q_3, δ(q_2,b)=q_4,δ(q_3,b)=q_5,δ(q_4,b)=q_5,δ(q_5,b)=q_5`
és kell még mindegyikhez ilyen: `δ(q_n,c)=q_n`
A második egyszerűbb, gondolom meg tudod csinálni. Két végállapota van.
Végül a direkt szorzat már triviális, csak sokat kell hozzá írni.
Persze ez akkor igaz, ha a `|w|_a` jelölés azt jelenti, hogy a `w` szóban lévő `a` szimbólumok száma. Bizonyára azt jelenti...
Szóval mondjuk `aaaaa` egy jó szó, `aaba` szintén, `b baa` szintén, stb.
Csinálj két automatát, az egyik számolja ezt az összeget, a másik meg azt nézze, hogy hárommal nem osztható darab c van-e. Aztán ennek a két automatának kell venni a direkt szorzatát.
Az első automata ilyesmi lehet:
`q_0` a kiinduló állapot, `q_5` az elfogadó.
Hint: A `q_n` állapot (`n=0,1,2,3,4`) azt jelenti, hogy a `|w|_a + 2*|w|_b` összeg éppen `n`. A `q_5` meg azt jelenti, hogy `≥ 5`.
`δ(q_0,a)=q_1, δ(q_1,a)=q_2, δ(q_2,a)=q_3,δ(q_3,a)=q_4,δ(q_4,a)=q_5,δ(q_5,a)=q_5`
`δ(q_0,b)=q_2, δ(q_1,b)=q_3, δ(q_2,b)=q_4,δ(q_3,b)=q_5,δ(q_4,b)=q_5,δ(q_5,b)=q_5`
és kell még mindegyikhez ilyen: `δ(q_n,c)=q_n`
A második egyszerűbb, gondolom meg tudod csinálni. Két végállapota van.
Végül a direkt szorzat már triviális, csak sokat kell hozzá írni.
1
- Még nem érkezett komment!