A hierarchy of random context grammars and automata

**Authors:**Ehlers, Elizabeth Marie**Date:**2014-04-03**Subjects:**Machine theory , Formal languages , Artificial intelligence**Type:**Thesis**Identifier:**uj:10501 , http://hdl.handle.net/10210/10004**Description:**Ph.D. (Computer Science) , Traditionally a formal language can be characterized in two ways: by a generative device (a grammar) and an acceptive device (an automaton). The characterization of two- and three-dimensional Random Context Grammars by two- and three-dimensional Random Context Automata are investigated. This thesis is an attempt to progressively extend a certain class of grammars to higher dimensions where the class of languages generated in each dimension is contained in the class of languages generated in the next higher dimension. Random Context Array Automata which characterizes Random Context Array Grammars (Von Solms [4,5]) are defined. The power of both Random Context Array Grammars and Random Context Array Automata is inherent in the fact that the replacement of symbols in figures is subject to horizontal, vertical and global context. A proof is given for the equivalence of the class of languages generated by Random Context Array Grammars and the class of languages accepted by Random Context Array Automata. The two-dimensional Random Context Array Grammars are extended to three dimensions. Random Context Structure Grammars generate three-dimensional structures. A characteristic of Random Context Structure Grammars is that the replacement of symbols in a structure is subject to seven relevant contexts. Random Context Structure Automata which characterize Random Context Structure Grammars are defined. It is shown that the class of languages generated by Random Context Structure Grammars are equivalent to the class of languages accepted by Random Context Array Automata...**Full Text:**

**Authors:**Ehlers, Elizabeth Marie**Date:**2014-04-03**Subjects:**Machine theory , Formal languages , Artificial intelligence**Type:**Thesis**Identifier:**uj:10501 , http://hdl.handle.net/10210/10004**Description:**Ph.D. (Computer Science) , Traditionally a formal language can be characterized in two ways: by a generative device (a grammar) and an acceptive device (an automaton). The characterization of two- and three-dimensional Random Context Grammars by two- and three-dimensional Random Context Automata are investigated. This thesis is an attempt to progressively extend a certain class of grammars to higher dimensions where the class of languages generated in each dimension is contained in the class of languages generated in the next higher dimension. Random Context Array Automata which characterizes Random Context Array Grammars (Von Solms [4,5]) are defined. The power of both Random Context Array Grammars and Random Context Array Automata is inherent in the fact that the replacement of symbols in figures is subject to horizontal, vertical and global context. A proof is given for the equivalence of the class of languages generated by Random Context Array Grammars and the class of languages accepted by Random Context Array Automata. The two-dimensional Random Context Array Grammars are extended to three dimensions. Random Context Structure Grammars generate three-dimensional structures. A characteristic of Random Context Structure Grammars is that the replacement of symbols in a structure is subject to seven relevant contexts. Random Context Structure Automata which characterize Random Context Structure Grammars are defined. It is shown that the class of languages generated by Random Context Structure Grammars are equivalent to the class of languages accepted by Random Context Array Automata...**Full Text:**

Automatically presentable structures

**Authors:**Ras, Charl John**Date:**2012-09-03**Subjects:**Sequential machine theory , Automata , Formal languages , Equivalence relations (Set theory) , Permutation groups , Graph theory , Numbers, Natural , Logic, Symbolic and mathematical**Type:**Thesis**Identifier:**uj:3443 , http://hdl.handle.net/10210/6838**Description:**M.Sc. , In this thesis we study some of the propertie of a clas called automatic structures. Automatic structures are structures that can be encoded (in some defined way) into a set of regular languages. This encoding allows one to prove many interesting properties about automatic structures, including decidabilty results.**Full Text:**

**Authors:**Ras, Charl John**Date:**2012-09-03**Subjects:**Sequential machine theory , Automata , Formal languages , Equivalence relations (Set theory) , Permutation groups , Graph theory , Numbers, Natural , Logic, Symbolic and mathematical**Type:**Thesis**Identifier:**uj:3443 , http://hdl.handle.net/10210/6838**Description:**M.Sc. , In this thesis we study some of the propertie of a clas called automatic structures. Automatic structures are structures that can be encoded (in some defined way) into a set of regular languages. This encoding allows one to prove many interesting properties about automatic structures, including decidabilty results.**Full Text:**

Using formal languages in data communications protocols

**Authors:**Mulder, Petrus Gerhardus**Date:**2014-05-19**Subjects:**Formal languages , Computer network protocols , Computer networks**Type:**Thesis**Identifier:**uj:11124 , http://hdl.handle.net/10210/10711**Description:**D.Phil. (Computer Science) , Please refer to full text to view abstract**Full Text:**

**Authors:**Mulder, Petrus Gerhardus**Date:**2014-05-19**Subjects:**Formal languages , Computer network protocols , Computer networks**Type:**Thesis**Identifier:**uj:11124 , http://hdl.handle.net/10210/10711**Description:**D.Phil. (Computer Science) , Please refer to full text to view abstract**Full Text:**

- «
- ‹
- 1
- ›
- »