Learn Easy

  Kumaraguru College of Technology, Coimbatore Department of Computer Science and Engineering U18CST4003 – Theory of Computation Chomsky Hierarchy of languages Work Sheet 1.1   Given the following, identify the grammar types a.     bAa  →   aa     S  →  s   Type 0 Grammar b.     S  →   AT     T  →   xy    A  →   a   Type 2 grammar c.      A  →   aBb     A  →   b    B  →   a   Type 2 grammar d.     S –> ab Type 2 grammar e.      S –> AB AB –> abc B –> b Type 1 grammar f.      Sab –> ba A –> S Type 0 Grammar Note:  We say that a grammar belong to a particular type of grammar when all its productions belongs to that type.

1.  Alphabet     An alphabet is a finite, non-empty set of symbols. The symbol  ∑  is used for representing it. Example:  Binary language: Alphabet = {0, 1} English language: Alphabet = {a, b, c, ...,z} 2. String A string is a finite sequence of symbols chosen from some alphabet.  Example: 101101 is a string that belongs to binary language. 2.1 Empty string Empty string is a string with zero occurrences of symbols. It is denoted by the symbol  ε.  2.2 Length of the string The length of the string is the number of characters occurring in any given string. Example: The length of the string 10110 is 5. We denote the length of the string s=10110 as |s|. 2.3 Powers of an alphabet The power of an alphabet  ∑ is represented as ∑ k  where k represents length of the the set of strings. Example: ∑  0   =  ε ∑  1   = {1, 0} ∑  2  = {01, 00, 11, 10} Special cases: Kleene closure ( ∑  * ) =  ∑  0 U ∑  1 U ∑  2 U …. Positive Closure   ( ∑  + ) =  ∑  1  U  ∑  2  U …. 3. Language The set of strings ch

 Chomsky classified the grammars into four types. They are Type-0, Type-1, Type-2 and Type-3. This is shown in the following diagram The description of these grammars are given in the following section 1. Type-0 Grammar Type-0 grammars represents exactly the languages recognized by the Turing Machine. This is also called as unrestricted or phrase-structured grammar. The general structure of this grammar is given below, where both the left and right hand side of the production may contain any number of terminals and variables. Example 1.1:  S -> ACaB                               Bc -> acB                               CB -> DB                                aD -> Db 2. Type-1 Grammar Type-1 grammars denotes the languages recognized by the Linear Bounded Automaton (LBA). The general structure of this grammar is given below, where the left and right side of the production consists of any number of terminal (T) and non-terminal (V) symbol, but    must contain a non-terminal. T