Introduction to Introduction to Introduction to Introduction to Languages and Languages and Languages and Languages and GrammarsGrammarsGrammarsGrammarsAlphabets and LanguagesAn alphabet is a finite non-empty set.Let S and T be alphabets.S • T = { s t | s ε S, t ε T }(We’ll often write ST for S•T.)λ = empty string, string of length oneS0= {λ }S1= SSn= S(n-1)• S, n > 1S+= S1U S2U S3U . . .S* = S0U S+A language L over an alphabet S is a subset of S*.How Many Languages Are There?• How many languages over a particular alphabet are there?Uncountably infinitely many!• Then, any finite method of describing languages can not include all of them.• Formal language theory gives us techniques for defining some languages over an alphabet.Why should I care about ?• Concepts of syntax and semantics used widely in computer science:• Basic compiler functions• Development of computer languages• Exploring the capabilities and limitations of algorithmic problem solvingMethods for Defining Languages• Grammar– Rules for defining which strings over an alphabet are in a particular language• Automaton (plural is automata)– A mathematical model of a computer which can determine whether a particular string is in the languageDefinition of a Grammar• A grammar G is a 4 tuple G = (N, Σ, P, S), where– N is an alphabet of nonterminal symbols– Σ is an alphabet of terminal symbols– N and Σ are disjoint– S is an element of N; S is the start symbol or initial symbol of the grammar– P is a set of productions of the form α -> β where• α is in (N U Σ)* N (N U Σ)*• β is in (N U Σ)*Definition of a Language Generated by a GrammarWe define => byγ α δ => γ δ β if α -> β is in P, andγ and δ are in (N U Σ)*=>+ is the transitive closure of =>=>* is the reflexive transitive closure of =>The language L generated by grammar G = (N, Σ, P, S), is defined byL = L(G) = { x | S *=> x and x is in Σ* }Classes of Grammars (The Chomsky Hierarchy)• Type 0, Phrase Structure (same as basic grammar definition)• Type 1, Context Sensitive– (1) α -> β where α is in (N U Σ)* N (N U Σ)*,• β is in (N U Σ)+, and length(α) ≤ length(β)– (2) γ A δ -> γ β δ where A is in N, β is in (N U Σ)+, and• γ and δ are in (N U Σ)*• Type 2, Context Free– A -> β where A is in N, β is in (N U Σ)*• Linear– A-> x or A -> x B y, where A and B are in N and x and y are in Σ*• Type 3, Regular Expressions– (1) left linear A -> B a or A -> a, where A and B are in N and a is in Σ– (2) right linear A -> a B or A -> a, where A and B are in N and a is in ΣComments on the Chomsky Hierarchy (1)• Definitions (1) and (2) for context sensitive are equivalent.• Definitions (1) and (2) for regular expressions are equivalent.• If a grammar has productions of all three of the forms described in definitions (1) and (2) for regular expressions, then it is a linear grammar.• Each definition of context sensitive is a restriction on the definition of phrase structure.• Every context free grammar can be converted to a context sensitive grammar with satisfies definition (2) which generates the same language except the language generated by the context sensitive grammar cannot contain the empty string λ.• The definition of linear grammar is a restriction on the definition of context free.• The definitions of left linear and right linear are restrictions on the definition of linear.Comments on the Chomsky Hierarchy• Every language generated by a left linear grammar can be generated by a right linear grammar, and every language generated by a right linear grammar can be generated by a left linear grammar.• Every language generated by a left linear or right linear grammar can be generated by a linear grammar.• Every language generated by a linear grammar can be generated by a context free grammar.• Let L be a language generated by a context free grammar. If L does not contain λ, then L can be generated by a context sensitive grammar. If L contains λ, then L-{λ} can be generated by a context sensitive grammar.• Every language generated by a context sensitive grammar can be generated by a phrase structure grammar.Example : A Left Linear Grammar for Identifiers• S -> S a• S -> S b• S -> S 1• S -> S 2• S -> a• S -> b• S => a• S => S 1 => a 1• S => S 2 => S b 2 => S 1 b 2 => a 1 b 2Example : A Right Linear Grammar for Identifiers• S -> a T• S -> b T• S -> a• S -> b• T -> a T• T -> b T• S => a• S => a T => a 1• S => a T => a 1 T=> a 1 b T => a 1 b 2T -> 1 TT -> 2 TT -> aT -> bT -> 1T -> 2Example: A Right Linear Grammar for {anbmcp| n, m, p > 0}• S -> a A• A -> a A• A -> b B• B -> b B• B -> c C• B -> c• C -> c C• C -> cS => a A => a a A=> a a a A=> a a a b B=> a a a b c C=> a a a b c cExample : A Linear Grammar for { anbn| n >0 }• S -> a S b• S -> a bS => a S b=> a a S b b=> a a a S b b b=> a a a a b b b bExample : A Linear Grammar for {anbmcmdn| n > 0}(Context Free Grammar)• S -> a S b• S -> a T b• T -> c T d• T -> c dS => a S b=> a a S b b=> a a a T b b b=> a a a c T d b b b=> a a a c c d d b b bAnother Example :A Context Free Grammar for {anbncmdm| n > 0}• S -> R T• R -> a R b• R -> a b• T -> c T d• T -> c dS => R T=> a R b T=> a a R b b T=> a a a b b b T=> a a a b b b c T d=> a a a b b b c c d dA Context Free Grammar for Expressions• S -> E • E -> E + T• E -> E - T• E -> T• T -> T * F• T -> T / F• T -> F• S => E => E + T– => E - T + T – => T - T + T – => F - …