Es sei ´L sube {a}^**´ eine nichtleere reguläre Sprache. Beweise, dass es natürliche Zahlen ´0 <= r_1 < r_2 < cdots < r_n < s_1 < s_2 < cdots < s_m´ mit ´n >= 0´ und ´m >= 0´ und eine natürlich Zahl ´p >= 0´ derart gibt, dass ´L = {a^(r_1), a^(r_2), …, a^(r_n)} uu {a^p}^** {a^(s_1), a^(s_2), …, a^(s_m)}´ gilt.
Es sei ´A = ({a}, Z, z_0, F, delta)´ ein deterministischer endlicher Automat, der ´L´ akzeptiert. Wir betrachten die Zustände ´z_r = delta(z_0, a_r)´. Da ´Z´ endlich ist, gibt es natürliche Zahlen ´s´ und ´t´ mit ´t < s´ so, dass
´z_i != z_j´ für ´1 <= i < j < s, z_s = z_t´
gelten. Offenbar gilt dann ´z_(s+i) = z_(t+i)´ für ´i >= 0´ und damit ´z_(s+i) = z_(t+k)´ mit ´k = i mod (s−t)´ für ´i >= 0´. Folglich ist
´Z = {z_0, z_1, …, z_t, z_(t+1), …, z_(s−1)}´.
Es sei
´F = {z_(r_1), z_(r_2), …, z_(r_n), z_(s_1), z_(s_2), …, z_(s_m)}´ mit ´0 <= r_i <= t−1´, ´t <= s_j <= s−1´.
Dann gilt offensichtlich:
´L = {a^(r_1), a^(r_2), …, a^(r_n)} uu {a^(s−t)}^(**) {a^(s_1), a^(s_2), …, a^(s_m)}´
HPI, 2014-06-26, Theoretische Informatik 2, Blatt 11, Aufgabe 1
2014-07-23 12:50:36 UTC
2014-07-23 12:50:36 UTC