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

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

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

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

4、任何狀態(tài)機(jī)均可以完全化本章主要討論了完全狀態(tài)機(jī)范疇的性質(zhì)先驗(yàn)證了所有的完全狀態(tài)機(jī)可以構(gòu)成一個(gè)范疇?并討論了這個(gè)范疇的始對象、終對象、和零對象的問題.再給出了完全狀態(tài)機(jī)范疇的同態(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→?是?中