Page 1
Regular Languages
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer Engineering
Lecture 3
Comments, additions and modifications
by Marek Perkowski
Page 2
Regular Languages
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer Engineering
Lecture 3
Comments, additions and modifications
by Marek Perkowski
Languages
• Informal Languages
– English
– Body
– Bureaucratize
• Formal Languages
– Rule-based
– Elements are decidable
– No deeper understanding required
Page 3
Regular Languages
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer Engineering
Lecture 3
Comments, additions and modifications
by Marek Perkowski
Languages
• Informal Languages
– English
– Body
– Bureaucratize
• Formal Languages
– Rule-based
– Elements are decidable
– No deeper understanding required
Formal Language
• All the Rules of the Language Are Explicitly
Stated in Terms of the Allowed Strings of
Symbols, e.g.,
– Programming languages, e.g., C, Lisp, Ada
– Military communications (formal “informal” L)
– Digital network protocols
Page 4
Regular Languages
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer Engineering
Lecture 3
Comments, additions and modifications
by Marek Perkowski
Languages
• Informal Languages
– English
– Body
– Bureaucratize
• Formal Languages
– Rule-based
– Elements are decidable
– No deeper understanding required
Formal Language
• All the Rules of the Language Are Explicitly
Stated in Terms of the Allowed Strings of
Symbols, e.g.,
– Programming languages, e.g., C, Lisp, Ada
– Military communications (formal “informal” L)
– Digital network protocols
A to ...
Alphabet: a finite set of symbols, aka I, S
– Roman: { a, b, c, ... , z }
– Binary: { 0, 1 }
– Greek: { a, ?, e, ?, ?, ?, ?, ... }
– Cyrillic: { ?, ?, ?, ?, ?, ... }
Page 5
Regular Languages
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer Engineering
Lecture 3
Comments, additions and modifications
by Marek Perkowski
Languages
• Informal Languages
– English
– Body
– Bureaucratize
• Formal Languages
– Rule-based
– Elements are decidable
– No deeper understanding required
Formal Language
• All the Rules of the Language Are Explicitly
Stated in Terms of the Allowed Strings of
Symbols, e.g.,
– Programming languages, e.g., C, Lisp, Ada
– Military communications (formal “informal” L)
– Digital network protocols
A to ...
Alphabet: a finite set of symbols, aka I, S
– Roman: { a, b, c, ... , z }
– Binary: { 0, 1 }
– Greek: { a, ?, e, ?, ?, ?, ?, ... }
– Cyrillic: { ?, ?, ?, ?, ?, ... }
String
String, word: a finite ordered sequence of
symbols from the alphabet, usually written
with no intervening punctuation
– x
1
= “ t h e “
– x
2
= “ 0 1 0 1 1 0 “
– x
3
= “
“
– x
4
= “ ? ? ? ? “
? ? ? a ? e t t a
Read More