Context free Grammars

Context free Grammars

Context free languages are used in parser design. They  play a vital role in compiler construction as well as in  describing the block structure in the programming  languages.

A CFG is a  quadruple (N, T, P, S).

N: Non terminal symbols

T: Terminal symbols

P: Prodcution rules

S: Start symbol

To generate a string start with the start symbol. Than replace the non termial symbols with terminals or non terminal symbols. Repeat the process untill all the nont terminals have been replaced by the terminals.

Example:

CFG:

S--> aABS

A-->a

B-->b

In this exammple,

N:= {S,A,B}

T:= {a,b}

P:= {S-->aABS, A-->a, B-->b}

S: = {S}

Related topics :

1. Definition of DFA
2. DFA notations
3. How DFA process inputs
4. DFA solved examples
5. Minimization of DFA
6. Definition of NFA
7. Equivalent of DFA and NFA
8. Properties of transition functions
9. Trape/ Dead state
10. Moore machine
11. Mealy machine
12. Mealy to Moore machine conversion
13. Moore to Mealy machine conversion
14. Difference between Mealy and Moore machine
15. Regular expression
16. Regular expression examples
17. Regular expresstion to CFG
18. Regular expression to Regular grammar
19. Ambiguous grammar
20. Leftmost and Rightmost derivations
21. Arden's Law
22. NFA with ∈ moves
23. Construct NFA without ∈ moves
24. NFA with ∈ to DFA Indirect method
25. Context Free Grammars
26. Convert CFG in to CNF
27. CFL are not closed under intersection