形式语言ch1.pdf

Formal Language And Automata  Languages  Autamata  Computation 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 = 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 Some vocabulary An alphabet Σ is a finite set (e.g., Σ = {0,1}) A string over Σis a finite length sequence of elements of Σ Σ* = the set of all strings over Σ For string x, |x| is the length of x The unique string of length 0 is denoted by ε and is called the empty string A language over Σis a set of strings over Σ In other words: a language is a subset of Σ* Examples of language example 1.1 alphabet : {0,1} L={w|w 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 Examples of language example 1.2 rule rule L={ 0n1n | n 0 }