Result Details

The Left-Most Derivation of Type Two in Matrix Grammars

ŠKRKAL, O. The Left-Most Derivation of Type Two in Matrix Grammars. Proceedings of 9th Conference and Competition Student EEICT 2003. Brno: Faculty of Electrical Engineering and Communication BUT, 2003. p. 566-570. ISBN: 80-214-2379-X.

Type

conference paper

Language

English

Authors

Škrkal Oto, Ing., FIT (FIT)

Abstract

This contribution discusses the descriptional complexity of matrixgrammars using left-most derivation of type two with respect to thenumber of nonterminals and matrices with two or more productions. Itproves that these matrix grammars need only nine nonterminals and sixmatrices of length two or more to generate recursively enumerablelanguages.

Keywords

Formal language theory, regulated rewriting, matrix grammars, canonical derivations, complexity reduction.

Published

2003

Pages

566–570

Proceedings

Proceedings of 9th Conference and Competition Student EEICT 2003

Conference

STUDENT EEICT 2003

ISBN

80-214-2379-X

Publisher

Faculty of Electrical Engineering and Communication BUT

Place

Brno

BibTeX

@inproceedings{BUT13992,
  author="Oto {Škrkal}",
  title="The Left-Most Derivation of Type Two in Matrix Grammars",
  booktitle="Proceedings of 9th Conference and Competition Student EEICT 2003",
  year="2003",
  pages="566--570",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  address="Brno",
  isbn="80-214-2379-X"
}

Departments

Department of Information Systems (DIFS)