Research On The Properties Of Some Codes In Formal Language And Automata Theory

Xu JiaoComputer Application Technology Academic MasterDirected by Di YangIn this paper,two main research contents are shown.In the first study,we will prove that the monoid generated by all irreducible prefix languages in connection with the set of d-primitive words is neither a free monoid,but the monoid generated by an irreducible prefix language in connection with the set of d-primitive words is a free monoid.Therefore,we obtain a free monoid containing prefix codes and d-primitive words,which enriches the research on prefix codes and free monoids.In the second study,we give the necessary and sufficient conditions for a special kind of three element language to be code.Let x,y,z are three different words over the alphabet and | x|,|y|,|z| are their lengths respectively.When| x|(28)| y|(27)|z| ?2 | x|,we give a necessary and sufficient condition for the language {x,y,z} to be a code.This conclusion greatly simplifies the previously complicated and difficult process of judging whether a three-element language is a code or not.