3ROLWHFKQLND&] VWRFKRZVND

:\G]LDá%XGRZ\0DV]\Q

,QIRUPDW\ND=DRF]QLH

- ]\NLIRUPDOQHLWHRULDDXWRPDWyZ

Ä$OJRU\WP\PLQLPDOL]DFMLDXWRPDWyZDNFHSWRUyZ5DELQD6FRWWD´

%RU\FNL'DULXV]

.RZDOF]\N6WDQLVáDZ

URN,,*UXSD,

&] VWRFKRZD

:SURZDG]HQLH

=DJDGQLHQLHPLQLPDOL]DFMLOLF]E\VWDQyZDXWRPDWXVSURZDG]DVL GR]QDOH]LHQLD

DXWRPDWX]GROQHJRGRZ\NRQDQLDSU]\QDMPQLHMWDNLHMSUDF\NWyU PR*HZ\NRQDüGDQ\

DXWRPDWPDMF\PR*OLZLHQDMPQLHMV] OLF]E VWDQyZ.RQLHF]QHMHVWZL FFLVáH

VSUHF\]RZDQLHFRWR]QDF]\*HSHZLHQDXWRPDWMHVW]GROQ\GRZ\NRQDQLDSU]\QDMPQLHMWDNLHM

SUDF\NWyU Z\NRQXMHLQQ\DXWRPDWRUD]SRGDQLHPHWRG\Z\]QDF]DQLDWDNLHJRDXWRPDWX

3URVW\SU]\NáDGDXWRPDWXDNFHSWRUD5DELQD6FRWWDRUD]MHJRPLQLPDOL]DFMD

:DXWRPDWDFKDNFHSWRUDFK5DELQD6FRWWD]DZV]HMHVWRNUHORQ\VWDQSRF]WNRZ\RUD]

]DZV]HRNUHODVL VWDQNRFRZ\:NRFXSUDF\DNFHSWRUDGRZLDGXMHP\VL F]\GDQHVáRZR

MHVWSU]H]QLHJRDNFHSWRZDQH

$XWRPDWHPDNFHSWRUHP5DELQD6FRWWDQD]\ZDP\XSRU]GNRZDQ SLWN NWyUDVNáDGD

VL ] $ ^&66 G)`

JG]LH ;±]ELyUV\JQDáyZOLWHUZHMFLRZ\FKDOIDEHWZHMFLRZ\

6±]ELyUVWDQyZZHZQ WU]Q\FK

6 ±]ELyUVWDQyZSRF]WNRZ\FK

G IXQNFMDSU]HMFLRZD

)±]ELyUVWDQyZNRFRZ\FK

G MHVWUHODFMG ;[6!6N G ;N6N

2]QDF]HQLHVWDQyZSRF]WNRZ\FK L

2]QDF]HQLHVWDQyZNRFRZ\FK

M

$XWRPDWDNFHSWRUDNFHSWXMHVáRZRMHOLZF]\WXMFMHRGVWDQXSRF]WNRZHJRGRMG]LH

GRNRFDGRVWDQXNRFRZHJR

; !

6 $%&'!

6

VWDUW

$!

$

%

&

) '

.D*G\DNFHSWRUSRVLDGDM ]\NVNáDGDMF\

VL ]HVáyZSU]H]QLHJRDNFHSWRZDQ\FK

'

$OJRU\WPPLQLPDOL]DFMLWHJRDNFHSWRUD

; !

6 $%&'!

6 $!

) '

.52.

V?[

:\SLVXMHP\VWDQ\NRFRZH

$

%

&

$'%'&'

%

%

&

1LHPR*QDLFKáF]\üER]OLNZLGXMHP\VWUXNWXU DXWRPDWX

&

&

'

'

$

'

.52.

6SUDZG]DP\SDU\

%

& ; ;

$%

$&

&%

' ; ; ;

/$ %

/$ %

/& &

$ % &

/% %

/& &

/% %

/$ &

/$ &

/& '

/% &

/& '

/% &

3RPLQLPDOL]DFMLE G QDVW SXMFHVWDQ\

6?[

$% $% &

&

&

'

'

$% '

Document Outline

  • Jêzyki formalne i teoria automatów.
    • „Algorytmy minimalizacji automatów akceptorów Rabina-Scotta”
      • 1. Wprowadzenie.
      • 2. Prosty przyk³ad automatu akceptora Rabina-Scotta oraz jego minimalizacja.