TOC Introduction Of Grammer<\/p>\n
[fvplayer id=”147″]<\/p>\n
In Theory of Computation (TOC)<\/strong>, Grammar<\/strong> is a set of rules that defines how strings in a language are formed. It is mainly used to generate and analyze formal languages.<\/p>\n A Grammar (G)<\/strong> in TOC is formally defined as: Where:<\/p>\n V (Variables\/Non-terminals):<\/strong> Set of symbols that can be replaced.<\/p>\n<\/li>\n T (Terminals):<\/strong> Set of symbols that appear in the final string.<\/p>\n<\/li>\n P (Production Rules):<\/strong> Rules that define how variables can be replaced by terminals or other variables.<\/p>\n<\/li>\n S (Start Symbol):<\/strong> The initial variable from which derivations begin.<\/p>\n<\/li>\n<\/ul>\n Consider a simple grammar: Production Rules:<\/strong> Generated Strings:<\/strong><\/p>\n This grammar generates a language of balanced Noam Chomsky classified grammars into four types:<\/p>\n\u00a0What is Grammar in TOC?<\/strong><\/h3>\n
G = (V, T, P, S)<\/strong><\/p>\n\n
\u00a0Example of a Grammar<\/strong><\/h3>\n
G = ({S}, {a, b}, {S \u2192 aSb | ab}, S)<\/strong><\/p>\n
S \u2192 aSb<\/strong>
S \u2192 ab<\/strong><\/p>\n\n
ab<\/code> (using rule 2)<\/p>\n<\/li>\naabb<\/code> (using rule 1 followed by rule 2)<\/p>\n<\/li>\naaabbb<\/code> (using rule 1 twice and then rule 2)<\/p>\n<\/li>\n<\/ul>\na<\/code> and b<\/code> pairs (like ab<\/code>, aabb<\/code>, aaabbb<\/code>, etc.).<\/p>\n\u00a0Types of Grammar (Chomsky Hierarchy)<\/strong><\/h3>\n