img196

196

D3. Podstawowe pojęcia teorii języków formalnych i automatów

Zapis 6(q> 7) = (g',*?) oznacza, źe po przeczytaniu ciągu 7 € Sj z wejścia, transdjuser przechodzi ze stanu q do stanu q' i wypisuje ciąg rj € A* na wyjście.

Dla 7 G ciąg rj = ST(7) jest napisem wyjściowym wtedy i tylko wtedy, gdy istnieją ciągi

Ti) • • • >7* € EJ, r)iG A*, 9i,...,gjbGQ

takie, źe

1)    7 = Ti •• -7*.

2)    »? = m-m,

3)    %i,7i+i) = («+i,i»+i), » = o, 1,1, ?0 € Go.