Theory of Automata and CGFG for learning

Automata

1. Theory of Automata & Formal Languages KCA-201 Unit 3

2. Course Outline TAFL

3. Chomsky Classification of Grammar TAFL Grammar Type Grammar Language Machine Type 0 Un-restricted grammar Recursively enumerable language Turing Machine Type 1 Context-sensitive grammar Context sensitive language Linear Bounded Automation Type 2 Context-free grammar Context free language Pushdown Automata Type 3 Regular grammar Regular language Finite State Automation Grammar  G(V, T, P, S): used to generate a language. where, V  Variables T  Terminals P  Production Rule S  Start Symbol Example: S  aSB S  aB S  b V = {S, B} Capitals T = {a, b} Smalls S = {S}  P Note: Objective is to convert the given Production Rule into the sentential form (string with no variable).

4. Regular Grammar TAFL Example: S  aSB S  aB B  b S  aSB using (2) S  aaBB using (3) S  aabb sentential form Using derivation tree/parse tree,

5. Derivation Tree/Parse Tree TAFL Derivations mean replacing a given string’s non-terminal by the right-hand side of the production rule. The sequence of applications of rules that makes the completed string of terminals from the starting symbol is known as derivation. The parse tree is the pictorial representation of derivations. Therefore, it is also known as derivation trees. The derivation tree is independent of the other in which productions are used. A parse tree is an ordered tree in which nodes are labeled with the left side of the productions and in which the children of a node define its equivalent right parse tree also known as syntax tree, generation tree, or production tree. A Parse Tree for a CFG G =(V,∑, P,S) is a tree satisfying the following conditions − Root has the label S, where S is the start symbol. Each vertex of the parse tree has a label which can be a variable (V), terminal (Σ), or ε. If A → C1,C2……. Cn is a production, then C1,C2……. Cn are children of node labeled A. Leaf Nodes are terminal (Σ), and Interior nodes are variable (V). The label of an internal vertex is always a variable. If a vertex A has k children with labels A1,A2……. Ak , then A →

6. Regular Grammar TAFL A grammar is a regular grammar if it is either right linear grammar (RLG) or left linear grammar (LLG). A variable is present at right most. Example: A  α B | β V ={A, B} T ={ α , β } S ={A} A α B (B lies at the right). A variable is present at left most. Example: A  B α | β V ={A, B} T ={ α , β } S ={A} A B α (B lies at the left).

7. Context Free Grammar TAFL In formal language theory, a Context Free Language is a language generated by some Context Free Grammar. The set of all CFL is identical to the set of languages accepted by Pushdown Automata. Context Free Grammar is identified by 04 tuples as G = {V, Ʃ, P, S} where V = Set of variables or Non-terminal Symbols Ʃ = Set of terminal Symbols S = Start Symbol P = Production Rule Context Free Grammar has Production Rule of the form A  x, where A ϵ V and x ϵ (V U Ʃ)*. Example: For generating a language that generates equal number of a’s and b’s in the form a n b n , the Context Free Grammar will be defined as G = { (S, A), (a, b), (S  aAb , A  aAb | ϵ ), S } S  aAb S  aaAbb S  aaaAbbb S  aaa bbb S  a 3 b 3  a n b n Production Rule: A production rule has the form α  β , where α and β are strings on V U T and at least one symbol of α belongs to V.

8. Context Free Grammar  Practice Problems TAFL Construct the CFG for the language having any number of a’s over the set Ʃ = {a}. Try to recognize the language L for given CGF G ={S, {a, b}, S} S  aSb S  ab Construct the CFG for the regular expression (0 + 1)*. Construct a grammar for the language containing strings of at least two a’s over Ʃ = {a, b}. Construct a grammar generating L = w c w r where w ϵ {a, b}*. Construct CGF for the language L which has all the strings which are all palindrome over Ʃ = {a, b}. Construct CFG for the language in which there are no consecutive b’s, the strings may or may not have consecutive a’s. Recognize the context free language for the given CFG. S  aB | bA A  a | aS | bAA B  b | bS | aBB Construct CFG for the language containing all the strings of different first and last symbols over Ʃ = {0, 1}. Find the CFG for the following languages (with n>=0, m>=0, k>=0). L = {a n b n c k | k>=3} L = {a m b n c k | n = m or m <= k} Find the regular grammar for the language L ={a n b m | n+m is even}. Find a CFG for the following language L = {a n b 2n c m | n, m>=0}.

9. Context Free Grammar  Derivation TAFL Production rules are used to derive strings The generation of language using specific rule is called derivation. In each step, the left most variable in sentential form is replaced. Example: S  aAB A  bBb B  A | λ SabBbB replacing A first. In each step, the right most variable in sentential form is replaced. Example: S  aAB A  bBb B  A | λ SaAA replacing B first.

10. Context Free Grammar  Practice Questions TAFL Check whether string ‘ abaaba ’ can be derived from the given set of production rule: S aSa S  bSb S  a S  b S  ϵ 2. Check whether string ‘ aabab ’ can be derived from the given set of production rule: S aS | bA | a | b | ϵ A  aS | a | ϵ 3. Derive the string ‘ aabbabba ’ from the given set of production rule using leftmost and rightmost derivation: S aB | bA A  a | aS | bAA B  b | bS | aBB

11. Context Free Grammar  Ambiguity TAFL E  E + E | E × E | a, Derive a + a × a Left-most Derivation: E  E + E  a + E  a + E × E  a + a × E  a + a × a E  E × E  E + E × E  a + E × E  a + a × a Right-most Derivation: E  E + E  E + E × E  E + E × a  E + a × a  a + a × a E  E × E  E × a  E + E × a  E + a × a  a + a × a

12. Context Free Grammar  Ambiguity TAFL Example: Consider the following two Grammars< G1: S  SbS | a G2: S  aB | ab, A  AB | a, B  Abb | b Which of the following option is correct? Only G1 is ambiguous Only G2 is ambiguous Both G1 and G2 are ambiguous Both G1 and G2 are unambiguous

13. Context Free Grammar  Simplification TAFL Reduction of CFG: In CFG, sometimes all the production rules and symbols are not needed for the derivation of strings. Besides this, thee may also be some NULL productions and Unit productions. Elimination of these productions and symbols is called simplification of CFG. Simplification consists of the following steps: Reduction of CFG Removal of Unit productions Removal of Null productions

14. Context Free Grammar  Simplification TAFL Reduction of CFG: Reduction of CFG: CFG are reduced in two phases. Phase 1: Derivation of an equivalent grammar G’, from the CFG, G , such that each variable derives some terminal string. Procedure: Step 1: Include all symbols W 1 , that derives some terminal and initialize i = 1. Step 2: Include symbols W i+1 , that derives W i . Step 3: Increment i and repeat Step 2, until W i+1 = W i . Step 4: Include all production rules that have W i in it. Phase 2: Derivation of an equivalent grammar G’’, from the CFG, G’ such that each symbol appears in a sentential form. Procedure: Step 1: Include the Start symbol in Y 1 and initialize i = 1. Step 2: Include all symbols Y i+1 , that can be derived from Yi and include all production rules that have been applied. Step 3: Increment i and repeat Step 2, until Y i+1 = Y i

15. Context Free Grammar  Simplification TAFL Example 1: Find a reduced grammar equivalent to the grammar G, having production rules P: S  AC | B, A  a, C  c, E  aA | e Phase 1: T = {a, c, e} W 1 = {A, C, E} W 2 = {A, C, E, S} W 3 = {A, C, E, S} G’ = ({A, C, E, S}, {a, c, e}, P, {S}) P = S AC, A  a, C  c, E  aA | e Phase 2: Y 1 = {S} Y 2 = {S, A, C} Y 3 = {S, A, C, a, c} Y 4 = {S, A, C, a, c} G’’ = ({A, C, S}, {a, c}, P, {S}) P= S  AC, A  a, C  c

16. Context Free Grammar  Practice Questions TAFL S  AB | CA, B  BC | AB, A  a, C  aB | b S  aA | bB , A  aA | a, B  bB , D  ab | Ea , E  aC | d S  aS | A | C, A  a, B  aa, C  aCb

17. Context Free Grammar  Simplification TAFL Reduction of CFG: 2. Removal of Unit Productions: Any production rule of the form A  B where A, B ϵ Non-Terminals is called Unit Production. Procedure: Step 1: To remove A  B, add production A  x to the grammar rule whenever B  x occurs in the grammar. [x ϵ Terminal, x can be Null]. Step 2: Delete A  B from the grammar.. Step 3: Repeat from Step 1 until all Unit productions are removed. Example: S  XY, X  a, Y  Z | b, Z  M, M  N, N  a Y  Z, Z  M, M  N Since, N  a, we add M  a S  XY, X  a, Y  Z | b, Z  M, M  a, N  a Since, M  a, we add Z  a S  XY, X  a, Y  Z | b, Z  a, M  a, N  a Since, Z  a, we add Y  a S  XY, X  a, Y a| b, Z  a, M  a, N  a Removing unreachable symbols, S  XY, X  a, Y a| b

18. Context Free Grammar  Practice Questions TAFL S  0A | 1B | C, A  0S | 00, B  1 | A, C  01

19. Context Free Grammar  Simplification TAFL Reduction of CFG: 3. Removal of Null Productions: In a CFG, a Non-Terminal symbol ‘A’ is a nullable variable if there is a production A  ϵ or there is a derivation that starts at ‘A’ and leads to ϵ . (Like A ……….  ϵ ). Procedure: Step 1: To remove A  ϵ , look for all productions whose right side contains A Step 2: Replace each occurrences of ‘A’ in each of these productions with ϵ . Step 3: Add the resultant productions to the Grammar.

20. Context Free Grammar  Simplification TAFL Example: S  ABAC, A  aA | ϵ , B  bB | ϵ , C  c A  ϵ , B  ϵ To eliminate A  ϵ S  ABAC | ABC | BAC | BC A  aA | a B  bB | ϵ C  c To eliminate B  ϵ S  ABAC | ABC | BAC | BC | AAC | AC | C A  aA | a B  bB | b C  c

21. Context Free Grammar  Practice Questions TAFL S  XYX, X  0X | ϵ , Y  1Y | ϵ

22. Context Free Grammar  Conversion of RG To RE TAFL S  01S | 01 : (01)*01 S  0011s | 01 | 10 S  01A | B11, A  011A | 01, B  101B | 11 S  011A | 101B, A  110A | 00, B  11B | S

23. Context Free Grammar  Conversion of RG To FA TAFL Left Linear Grammar: S  01S | 1 S  011S | 01 S  001S | 10A, A  101A | 0 | 1 Right Linear Grammar: 1. S  S10 | 01

24. Context Free Grammar  Conversion of FA To RG TAFL

25. Normal Forms  Chomsky Normal Form TAFL In Chomsky Normal Form (CNF) we have a restriction on the length of RHS; which is; elements in RHS should either be two variables or a Terminal. A CFG is in CNF if the productions are in the following forms: A  a A  BC Where, A, B and C are non-terminals and ‘a’ is a terminal.

26. Normal Forms  Chomsky Normal Form TAFL