Formal Languages - Concatenation and Closure

Michał Trybulec

Formalized Mathematics (2007)

  • Volume: 15, Issue: 1, page 11-15
  • ISSN: 1426-2630

Abstract

top
Formal languages are introduced as subsets of the set of all 0-based finite sequences over a given set (the alphabet). Concatenation, the n-th power and closure are defined and their properties are shown. Finally, it is shown that the closure of the alphabet (understood here as the language of words of length 1) equals to the set of all words over that alphabet, and that the alphabet is the minimal set with this property. Notation and terminology were taken from [5] and [13]. MML identifier: FLANG 1, version: 7.8.04 4.81.962

How to cite

top

Michał Trybulec. "Formal Languages - Concatenation and Closure." Formalized Mathematics 15.1 (2007): 11-15. <http://eudml.org/doc/267464>.

@article{MichałTrybulec2007,
abstract = {Formal languages are introduced as subsets of the set of all 0-based finite sequences over a given set (the alphabet). Concatenation, the n-th power and closure are defined and their properties are shown. Finally, it is shown that the closure of the alphabet (understood here as the language of words of length 1) equals to the set of all words over that alphabet, and that the alphabet is the minimal set with this property. Notation and terminology were taken from [5] and [13]. MML identifier: FLANG 1, version: 7.8.04 4.81.962},
author = {Michał Trybulec},
journal = {Formalized Mathematics},
language = {eng},
number = {1},
pages = {11-15},
title = {Formal Languages - Concatenation and Closure},
url = {http://eudml.org/doc/267464},
volume = {15},
year = {2007},
}

TY - JOUR
AU - Michał Trybulec
TI - Formal Languages - Concatenation and Closure
JO - Formalized Mathematics
PY - 2007
VL - 15
IS - 1
SP - 11
EP - 15
AB - Formal languages are introduced as subsets of the set of all 0-based finite sequences over a given set (the alphabet). Concatenation, the n-th power and closure are defined and their properties are shown. Finally, it is shown that the closure of the alphabet (understood here as the language of words of length 1) equals to the set of all words over that alphabet, and that the alphabet is the minimal set with this property. Notation and terminology were taken from [5] and [13]. MML identifier: FLANG 1, version: 7.8.04 4.81.962
LA - eng
UR - http://eudml.org/doc/267464
ER -

References

top
  1. [3] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  2. [4] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  3. [5] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979. Zbl0426.68001
  4. [6] Beata Padlewska. Families of sets. Formalized Mathematics, 1(1):147-152, 1990. 
  5. [7] Karol Pąak. The Catalan numbers. Part II. Formalized Mathematics, 14(4):153-159, 2006. 
  6. [8] Andrzej Trybulec. Subsets of complex numbers. To appear in Formalized Mathematics. 
  7. [9] Andrzej Trybulec. Domains and their Cartesian products. Formalized Mathematics, 1(1):115-122, 1990. 
  8. [10] Andrzej Trybulec. Tarski Grothendieck set theory. Formalized Mathematics, 1(1):9-11, 1990. 
  9. [11] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  10. [12] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825-829, 2001. 
  11. [13] William M. Waite and Gerhard Goos. Compiler Construction. Springer-Verlag New York Inc., 1984. Zbl0527.68003
  12. [14] Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990. 
  13. [1] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  14. [2] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.