哈尔滨工业大学形式语言课件slide_1-2009.pdfVIP

Formal Language  Automata  Computation  Languages Automata  Alan MarthisonTuring  On Computable Numbers With an Application to the Entscheidungs Problem  Turing Machine Automata  Finite Automata  Deterministic Finite Automata  Non-deterministic Finite Automata  Push Down Automata Language This is a sentence. What is a language ? This is also a sentence. …… So we have { sentence 1, sentence 2, sentence 3, …… } the set of sentences  Language Sentence and Alphabet sentence/string = sequence of symbols chosen from the alphabet  example : Mouse love rice. alphabet = finite set of symbols example : ASCII, ={0,1} symbols sentences  language Rules/Grammar  rules = by which sentence is generated example : rules for English sentence noun-phrasepredicate noun-phrase articlenoun predicate verb article a|an|the noun wolf|sheep verb love|eat Notation of language example : alphabet : {0,1} L={s|s consists of 0’s and 1’s, rule and end with 0 } L={ 0,00,10,000,010,100,110,0000,} L, 1L, 0001L, 20L Notation of language Another example : L={ 0n1n | n  1 } alphabet = {0,1} L={ 01, 0011, 000111, 0000011111 , } String operations w=a