狀態(tài)機的若干代數(shù)性質(zhì).pdf

1、廣西師范大學(xué)研究生學(xué)位論文狀態(tài)機的若干代數(shù)性質(zhì)狀態(tài)機的若干代數(shù)性質(zhì)OnAlgebraicPropertiesofStateMachines院系：數(shù)學(xué)與計算機科學(xué)學(xué)院年級：二○○一級學(xué)科專業(yè)：基礎(chǔ)數(shù)學(xué)研究方向：代數(shù)及其應(yīng)用導(dǎo)師：易忠教授鄧培民教授研究生：林莉完成時間：二○○四年四月二○○四年四月I狀態(tài)機的若干代數(shù)性質(zhì)狀態(tài)機的若干代數(shù)性質(zhì)2001級基礎(chǔ)數(shù)學(xué)專業(yè)代數(shù)及其應(yīng)用方向研究生林莉第一部分第一部分中文摘要中文摘要自動機就是自動化系統(tǒng)的模

2、型它作為一種有效的形式化工具無論是在理論還是在實踐中都有著重要的作用.自動機理論主要研究離散數(shù)字系統(tǒng)的功能、結(jié)構(gòu)及兩者關(guān)系旨在自動機的分析與綜合問題.隨著微電子及信息等科學(xué)技術(shù)的迅猛發(fā)展自動機理論已逐步向不同領(lǐng)域滲透成為許多學(xué)科的重要理論和應(yīng)用基礎(chǔ)狀態(tài)機是指無輸出的有限自動機.狀態(tài)機理論是有限自動機理論的一個研究方向.許多的國內(nèi)外學(xué)者借助不同的數(shù)學(xué)工具如微分方程、泛函分析、代數(shù)及概率論等對其進行討論促進了自動機理論的發(fā)展.本論文以代數(shù)為

3、工具對狀態(tài)機理論進行研究主要工作包括兩個:一個是使用范疇論的方法對固定輸入集的狀態(tài)機定義一個范疇討論它的性質(zhì)另一個是用矩陣代數(shù)的知識來刻畫有限交換環(huán)上的線性元胞自動機借此來分析其演化結(jié)構(gòu).第二部分是本文的主要結(jié)果共分成3章第1章是引言簡單介紹了自動機在計算機科學(xué)中的重要位置以及它與其它科學(xué)分支的密切關(guān)系.著重介紹了狀態(tài)機與元胞自動機的代數(shù)研究背景.并給出了狀態(tài)機和元胞自動機的基本概念和記號.第2章是關(guān)于完全狀態(tài)機范疇的性質(zhì)的研究.考慮到

4、任何狀態(tài)機均可以完全化本章主要討論了完全狀態(tài)機范疇的性質(zhì)先驗證了所有的完全狀態(tài)機可以構(gòu)成一個范疇?并討論了這個范疇的始對象、終對象、和零對象的問題.再給出了完全狀態(tài)機范疇的同態(tài)基本定理.所得主要結(jié)果如下:命題2.2.3命題2.2.3?中任一)(111FQMΣ=到)(222FQMΣ=的同態(tài)?的核?Ker是1M的相允關(guān)系若?為滿同態(tài)則?為同構(gòu)的充分必要條件是?Ker是1M上的單位相允.定理2.2.4定理2.2.4(1)設(shè)21:MM→?是?中