Theory of computation toc computer science

Toc computer science

1. Part 4 MISC TOPICS ACCS16706 Theory of Computations ER.PAVITAR SINGH

2. After going through this topic, you should be able to 1. Define LL(k) Grammar & Properties, 2. Define LR(k) Grammar & Properties, 3. Differentiate between LL(k) & LR(k) grammar, 4. Understand the concept of Decidability and Recursively Enumerable Languages. Topics Covered:

3. LL(K) Grammar: A context free grammar is called LL(K) for left to right scan, producing a leftmost derivation with k symbol look ahead if we can always make a correct decision by checking at most the first k symbols of “W”. Properties: A context free grammar is LL(K) grammar if by scanning an input string left to right, we can get a left most derivation by looking k symbols ahead. LL (1) grammars are successfully being used in compilers. LL(K) grammars are used in top down parsing. LL(K) grammars are weak as compared to LR(K). Every LL(K) grammar is non-ambiguous.

4. LR(K) Grammar: LR(K) grammars are used in syntax analysis phase of compiler. LR(K) grammars reduce the given string w to start symbol S by reducing. It scans the string from left to right and while reduction it gives reverse rightmost derivation of a string. E.g. if E  E +E | E*E | id Then string id + id * id can be reduced as: id + id * id E + id * id Right most derivation in reverse E + E * id E + E * E E + E E

5. Properties of LR(k): Every LR(K) grammar G is unambiguous. If G is an LR(K) grammar there exist a pushdown automata A acceptability L(G). If A is a deterministic PDA there exists an LR (1) grammar G such that L(G) = N(A). The class of deterministic language is said to be proper sub-class of the class of CFL. The class of deterministic language s can be denoted by L dcf1 is closed under complementation but not under union and intersection. 6. A CFL is generated by LR (0) grammar iff it is accepted by deterministic PDA and has prefix property.

6. Difference between LL(K) and LR(K) grammar. SNO  LL(K) LR(K) 1 L means Left to Right, L means using Left derivation K  Symbol look ahead. L means Left to Right, R producing right most derivation, K  Symbol look ahead. 2 It uses top down technique. It uses Bottom Up technique. 3 Parsing table is not used. Concept of parsing table is used. 4 Applied to grammar having less productions. Applied to wide class of grammar and languages. 5 No tool is used for LL(K) grammar. Well supported tools like YACC (Yet Another Compiler Compiler). 6 Language generated by LL(K) grammar is LL(K) language. LR(K) language is generated by LR(K) grammar. 7 LL(K) grammar is also known as predictive grammar or parsing. LR(K) grammar is also called as shift reduce parsing.

7. Recursive Language: A language is said to be recursive or decidable if there exist a Turing machine T such that If string ‘s’ in language i.e. s belongs to L then T accepts. If string ‘s’ is not in language i.e. s does not belong to L then T halts but it never enters an accepting state. A recursive language accepts every string of the language L and rejects every string over some alphabet that is not in the language. Let L is language imagine it as a problem then we can say a problem L is called decidable if it is recursive language and is called undecidable if it is not recursive.

8. Recursively enumerable Language: A Language L is said to be recursively enumerable language if there exists a Turing machine which will accept (and therefore halt) for all the input strings which are in ‘L’. But may or may not halt for all input strings which are not in ‘L’.  

9. Decidability A decision problem P is decidable if the language L of all yes instances to P is decidable. For a decidable language, for each input string, the TM halts either at the accept or the reject state as depicted in the following diagram –