Sequential-Machine-Theory Notes | EduRev

 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