Matematické Fórum

Nápad jak reprezentovat vícepáskový stroj je např. zde
http://forum.matweb.cz/viewtopic.php?id=7354
gramatiku už z toho odvodíš snadno.

↑ turcovsky:To já jsem byl včera koukám taky, že jsem si ani detailně nepřečetl zadání :)
Jestli tomu dobře rozumím, tak narozdíl od odkazovaného příkladu zde nekódujeme obsah pásky, ale celý stroj. Víme, že turingův stroj je uspořádaná devítice (S,G,Q,d,q_a,q_r,q_0, levá koncová značka a @ prázdné políčko (nebbo pravá koncová značka, záleží na přístupu.
Kořenový neterminál naší gramatiky bude M a bude mít přepisovací pravidlo
M -> S#G#Q#d#q_a#q_r#q_0#,@ jsou neterminály.
Abecedu S můžeme kódovat jako posloupnost symbolů, můžeme proto zvolit pravidla
S ->ZS
S->Z
kde Z lze přepsat na libovolný znak vstupní abecedy. Podobně
G -> NG
G -> N
kde N lze přepsat na libovolný znak z G.
Dále
$ -> N
@ -> N
Definujeme-li neterminál F, který se dá přepsat na označení libovolného stavu, máme
q_0 ->F
q_a -> F
q_r -> F
Q -> F
Q -> FQ
Teď máme zakódované všechno kromě přechodové funkce. Přechodová funkce přiřazuje n-tici znaků na páskách a stavu novou n-tci, nový stav a pro každou pásku také posunutí. Každý prvek lze proto napsat ve formátu #N#N#..#N#F#N#N#..#N#F#P#...#P#, kde první sada N-ek jsou načtené symboly, první F-ko načtený stav, druhá sada jsou vypsané symboly, druhé F výsledný stav a P je posunutí pro jednotlivé pásky. Přidáme proto pravidla
d->T
d->Td
T->#Z#Z#..#Z#F#Z#Z#..#Z#F#P#...#P#
P->left
P->right

Popsaná gramatika hlídá velmi málo věcí, neověří například, že je přechodová funkce definovaná všude, že q_a není současně q_r apod. Myslím ale, že přidání dalších podmínek tohoto typu by gramatiku naprosto znečitelnilo. Proto ne všechny stroje jí vygenerované budou korektní (ale všechny korektní stoje se s její pomocí dají vygenerovat).

Nebudu se úplně držet předchozího příspěvku, protože by tao pak začalo být moc slžité.

K zápisu stroje je nejdůležitější zapsat jeho přechodovou funkci. Ta je pro n-páskový stroj tvořena (3n+2)-ticemi
(stav,stav,znak,znak,L/R,znak,znak,L/R,....,znak,znak,L/r).
Na začátku je výchozí stav, pak vždy načtený znak, zapsaný znak, a posun hlavy pro každou pásku.
Zápis takové funkce pro n-páskový stroj nad danou pracovní abecedou tedy můžeme udělat takto:

F -> eps | MF
M -> (S,S,Z,Z,P,Z,Z,P,....,Z,Z,P)           -- zde ty tečky nahrazují počet pozic závislý na počtu pásek
P -> L | R
S -> Z | ZS | 0 | a | r
Z ->  vždy koncová. Zbývá proto specifikovat pouze vstupní abecedu stroje. To lze pravidly

A -> Z' | Z'A
Z' -> znak vstupní abecedy

Celý stroj pak můžeme zapsat např. pomocí takovéhoto neterminálu T

T -> (A)F

Zápis stroje pak může být např. (abcdef)(0,b,@,@,R,@,@,R)(a,b,a,a,L,b,b,L) -- takový stroj ale nedělá nic moc zajímavého (načte začátky vstupních pásek, posune se doprava a přejde do stavu, pokud bude na horní pásce a a na dolní pásce b, akceptuje, jinak zamítne.

Dobry den, chtel bych se zeptat, jestli by ta gramatika mohla vypadat nejak takhle. At premyslim jak premyslim, stale si s timto ukolem nevim moc rady a uz z toho celkem solidne vysiluju:-D
Nevim si moc rady s pravidlem pro prepis na vice stavu (A->) a o pravidlu pro prepis na vice znaku si take nejsem jisty(B->). Jeste by me zajimalo, jak v pravidle C-> "vyrobit" posuv pro vice pasek. Predem moc dekuji za jakoukoliv pomoc.
PS:Kdybyste jeste vedeli o nejakem vhodnem prikladu byl bych moc vdecny. Prechodovou fci mam δ ((qi, a) = (qj, b, +); (qk, b) = (ql, b, -))


G = (П, ∑, S, P)
П (S, A, B, C, D)
∑ (M, =, Q, Γ, δ, q0, F, □, qE, h, +, -, 0, (, ))
S (S)
S→     M = (Q, ∑, Γ, δ, q0, F)
Q(A)
∑(B)
Γ(□, B)
q0 = E
F = fF
δ (C)
A→    qE  | ??
B→    h | B | ε
H→    [a…z]B | FB |    ε
C→    (qE , h) = (qE, h, D) | C
D→    + | - | 0 | D   
E→     [0…9]E | qF | fF |  ε
F→    [0…9] | [0…9]F