Introduction to formal languages and automata

[jimin-kiim]

• Languages
• Grammars
• Automata

[jimin-kiim]

Languages

alphabet : set of symbols

string : a sequence of letters defined over an alphabet

string operations

• concatenation
• reverse
• length
• power : concatenating for several times
  • power of 0 is empty string
• star closure : the set of all possible strings from alphabet
• positive closure : star closure - empty string

empty string : a string with no symbols (length of the string is 0)

substring of string : a subsequence of consecutive characters

prefix and sufix

a language : any subset of star closure of alphabet

operations on languages

• union
• intersect
• difference
• complement
• reverse
• concatenation
• power
• star closure
• positive closure

[jimin-kiim]

Grammars

G = (V, T, S, P) V : a finite set of variables T : a finite set of terminal symbols S : a special symbol called start variable P : a finite set of productions

derivation of sentence(string) : producing a string(sentence) following the grammar rule sentential form : a sentence that contains variables and terminals

language of a grammar L(G) = { w: S *=> w} the language which is following the grammar

q->ap q: variable a: terminal p: variable

[jimin-kiim]

Automata

temporary memory, input memory, output memory, CPU, program memory

Automata

• Finite Automata : no temporary memory
• Pushdown Automata : using stack as temporary memory
• Turing Machine : random access memory as temporary memory

power of automata Finite Automata < Pushdown Automata < Turing Machine the more powerful, the more computational problems can be solved with