nieskończony automat skończony

2017.03.10 06:22
nieskończony automat skończony

Mam iteratora, który bez końca daje zera i jedynki, co sekundę, a do tego je wypisuje:

from random import randint
from time import sleep

def numbers():
    while True:
        i = randint(0, 1)
        print(i)
        yield i
        sleep(1)

numbers = numbers()

Chcę napisać program, który ma czytać te liczby i wypisywać znaczek "x", kiedy po zerze nastąpi jedynka. Ponieważ to jest zwykły automat skończony, to mam dwie możliwości: stan tego automatu moge trzymać albo eksplicytnie, w jakiejś zmiennej, albo implicytnie, w przepływie. Trzymanie eksplicytne wygląda tak:

from random import randint
from time import sleep

def numbers():
    while True:
        i = randint(0, 1)
        print(i)
        yield i
        sleep(1)

numbers = numbers()

while True:
    while next(numbers) != 1:
        pass
    print('x')
    while next(numbers) != 0:
        pass

A trzymanie eksplicytne wygląda tak:

from random import randint
from time import sleep

def numbers():
    while True:
        i = randint(0, 1)
        print(i)
        yield i
        sleep(1)

numbers = numbers()

state = 0
while True:
    number = next(numbers)
    if state == 0 and number == 1:
        state = 1
        print('x')
    if state == 1 and number == 0:
        state = 0

Jak interpreter wykonuje tego while'a, to jest takim automatem skończonym, który pamięta, na której jest linijce, i robi odpowiednią rzecz (jak interpreter wykonuje resztę programu to też jest prawie automatem skończonym, ale o tym teraz nie myślę). Ten automat ma sześć stanów:

from random import randint
from time import sleep

def numbers():
    while True:
        i = randint(0, 1)
        print(i)
        yield i
        sleep(1)

numbers = numbers()

state = 0                           # 0
while True:
    number = next(numbers)          # 1
    if state == 0 and number == 1:  # 2
        state = 1                   # 3
        print('x')                  # 4
    elif state == 1 and number == 0:# 5
        state = 0                   # 6

Więc można ten automat zaimplementować wprost, trzymając jego stan esplicytnie w zmiennej:

from random import randint
from time import sleep

def numbers():
    while True:
        i = randint(0, 1)
        print(i)
        yield i
        sleep(1)

numbers = numbers()

metastate = 0
state = None
number = None
while True:
    if metastate == 0:
        state = 0
        metastate = 1
    if metastate == 1:
        number = next(numbers)
        metastate = 2
    if metastate == 2:
        metastate = 3 if state == 0 and number == 1 else 5
    if metastate == 3:
        state = 1
        metastate = 4
    if metastate == 4:
        print('x')
        metastate = 1
    if metastate == 5:
        metastate = 6 if state == 1 and number == 0 else 1
    if metastate == 6:
        state = 0
        metastate = 1

A potem można tak robić dalej i dalej i dalej...

komentarze:

powrót na stronę główną

RSS