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

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

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

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

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