Konečné a zásobníkové automaty, Regulární výrazy

dema z knihoven komentuje

Marta Vomlelová

from automata.fa.dfa import DFA
dfa = DFA(
    states={'1','2','3'},
    input_symbols={'a','b'},
    transitions={
        '1':{'a':'2','b':'1'},
        '2':{'a':'3','b':'2'},
        '3':{'a':'2','b':'3'}
    },
    initial_state='1',
    final_states={'2'},
#    allow_partial=True
)
#dfa.show_diagram('dfa.png')

Zobrazení automatu

from IPython.display import Image, display

def view_pydot(pdot):
    plt = Image(pdot.create_png())
    display(plt)

view_pydot(dfa.show_diagram())

Přijme ve stavu

dfa.read_input('a')

'2'

Při nepřijetí by selhal, je nutné testovat

testování 'if'

input='aaa'
if dfa.accepts_input(input):
    print('delta({},"{}")= {}'.format(dfa.initial_state,input,dfa.read_input(input)))
else:
    print('Reject.')

delta(1,"aaa")= 2

Exceptions

import automata.base.exceptions as exceptions
try:
    print('delta({},"{}")= {}'.format(dfa.initial_state,input,dfa.read_input(input)))
except  exceptions.RejectionException:
    print('Reject')

delta(1,"aaa")= 2

Další metody

validate

minify(self, retain_names=False)

complement

union, difference, issubset

Nedeterministický automat

from automata.fa.nfa import NFA
nfa = NFA(
    states={'1','2','3'},
    input_symbols={'a','b'},
    transitions={
        '1':{'a':{'2'}},
        '2':{'a':{'2'},'b':{'2'}},
        '3':{'a':{'2'},'b':{'1','2'}}
    },
    initial_state='1',
    final_states={'2'}
)
try:
    mm=nfa.read_input('aa')
    print(mm)
except  exceptions.RejectionException:
    print('Reject')
list(nfa.read_input_stepwise('aa'))

{'2'}

[{'1'}, {'2'}, {'2'}]

Tato knihovna zobrazuje jen deterministické automaty

df2=DFA.from_nfa(nfa)
df2.show_diagram('df2.png')
view_pydot(df2.show_diagram())

Zajímavá metoda

reverse

Regulární výrazy

import re
import functools as fc
txt_list=[r'auto',r'abba',r'abbababbaa',r'abbaa',r'ababbaaaa',r'bb',r'aaaaaa'
          ,r'abbbbab',r'ttabvrett',r'aba',r'aaa',r'baaa'
          ]

Najde?

single_check=fc.partial(re.search, r'(ba)')
single_check(r'abba')

<re.Match object; span=(2, 4), match='ba'>

Výpis výrazu a všech nalezených skupin

for where in txt_list:
    ret_val=single_check(where)
    print('{} : {}'.format(where,ret_val))
    if ret_val != None:
        print(ret_val.groups())

auto : None
abba : <re.Match object; span=(2, 4), match='ba'>
('ba',)
abbababbaa : <re.Match object; span=(2, 4), match='ba'>
('ba',)
abbaa : <re.Match object; span=(2, 4), match='ba'>
('ba',)
ababbaaaa : <re.Match object; span=(1, 3), match='ba'>
('ba',)
bb : None
aaaaaa : None
abbbbab : <re.Match object; span=(4, 6), match='ba'>
('ba',)
ttabvrett : None
aba : <re.Match object; span=(1, 3), match='ba'>
('ba',)
aaa : None
baaa : <re.Match object; span=(0, 2), match='ba'>
('ba',)

Různé výrazy k testování a výsledky hledání

e1a=r'(abba)'
e1b=r'(^abb).*(bbaa$)|^abbaa|^abbbaa'
e1c=r'^(a[b-z]*a[b-z]*a[b-z]*)*[b-z]*$'
e1d=r'(?P<mmm>^..).*(?P=mmm)$|^(?P<mm>.)(?P=mm){1,2}$'
e1e=r'^[b-z]*(a[b-z]+)*a{0,1}$'
e2=r'(a|b)(a|b)*$'
e22=r'(a(?:a|b)*)$|(?:b(?:a|b)*)$'
exps=[e1a,e1b,e1c,e1d,e2,e22]

i=3
print(txt_list[i])
for exp in exps:
    print('{} : {}'.format(exp,re.search(exp,txt_list[i])))

abbaa
(abba) : <re.Match object; span=(0, 4), match='abba'>
(^abb).*(bbaa$)|^abbaa|^abbbaa : <re.Match object; span=(0, 5), match='abbaa'>
^(a[b-z]*a[b-z]*a[b-z]*)*[b-z]*$ : <re.Match object; span=(0, 5), match='abbaa'>
(?P<mmm>^..).*(?P=mmm)$|^(?P<mm>.)(?P=mm){1,2}$ : None
(a|b)(a|b)*$ : <re.Match object; span=(0, 5), match='abbaa'>
(a(?:a|b)*)$|(?:b(?:a|b)*)$ : <re.Match object; span=(0, 5), match='abbaa'>

Zásobníkový automat

vzorový příklad z knihovny automata

# example 
from automata.pda.dpda import DPDA
# DPDA which which matches zero or more 'a's, followed by the same
# number of 'b's (accepting by final state)
dpda = DPDA(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'a', 'b'},
    stack_symbols={'0', '1'},
    transitions={
        'q0': {
            'a': {'0': ('q1', ('1', '0'))}  # transition pushes '1' to stack
        },
        'q1': {
            'a': {'1': ('q1', ('1', '1'))},
            'b': {'1': ('q2', '')}  # transition pops from stack
        },
        'q2': {
            'b': {'1': ('q2', '')},
            '': {'0': ('q3', ('0',))}  # transition does not change stack
        }
    },
    initial_state='q0',
    initial_stack_symbol='0',
    final_states={'q3'},
    acceptance_mode='final_state'
)

Postupný výpis kroků

všiměte si pořadí na zásobníku: v zadání vrch vlevo, ve výpisu vrch vpravo.

list(dpda.read_input_stepwise('aabb'))

[PDAConfiguration('q0', 'aabb', PDAStack('0',)),
 PDAConfiguration('q1', 'abb', PDAStack('0', '1')),
 PDAConfiguration('q1', 'bb', PDAStack('0', '1', '1')),
 PDAConfiguration('q2', 'b', PDAStack('0', '1')),
 PDAConfiguration('q2', '', PDAStack('0',)),
 PDAConfiguration('q3', '', PDAStack('0',))]