Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests - Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests -
× DOWNLOAD NOW

Context Sensitive Grammar (CSG)

A formal grammar known as a CSG allows any production rules’ left and right sides to be surrounded by a context of the terminal as well as nonterminal symbols.

In this article, we will look more into Context Sensitive Grammar according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.

Table of Contents

What is Context Sensitive Grammar (CSG)?

CSG is a 4 tuple grammar G. Here, G = (V, Σ, R, S), where:

  • Σ refers to the element’s finite set known as terminals.
  • V refers to the element’s finite set known as variables.
  • S refers to V’s element, and it is known as the start variable.
  • V ∩ Σ = Null (empty set).
  • R refers to a fine element’s set known as Production Rules. Every rule is like xXy -> xby in which the X is in V, b is in (V union Σ)+, and x and y are in (V union Σ).

Please take note that the Production Rules R are the only area where Context Free Grammar differs.

Only for the starting symbol that appears only on the rule’s left side is the rule S -> empty permitted.

Properties of Context Sensitive Grammar

Properties of Context Sensitive Grammar are:

  • All CFLs are CSLs (Context Sensitive Languages).
  • Not all CSLs are CFLs.
  • A weakly similar Kuroda Normal Form Context Sensitive Grammar can be created from any Context Sensitive Grammar (CSG) that does not produce an empty string. Weakly equivalent means that the set of CSL produced by both Context Sensitive Grammars is the same.
  • If and only if the language’s strings are accepted by a linear bounded automaton (LBA), the language is formed using Context Sensitive Grammar.
  • A PSPACE-complete algorithm exists to determine whether a given Context Sensitive Grammar G can generate a given string, STR. This indicates that the problem is difficult, and if it can be solved in polynomial time, it will imply that P = NP, a long-standing issue in computer science.

Application of Context Sensitive Grammar

The grammar that is Context Sensitive is more effective than grammar that is context-free. Context Sensitive Grammar can be used to create Natural Language, whereas Context Free Grammar cannot.

Context Sensitive Grammar has the following issues:

  • The grammar required for Natural Language is substantially weaker than CSG.
  • The CSG decision problem is PSPACE-complete.

Because every Natural Language may be modelled as a CSG, Context Sensitive Grammar is not typically used to generate Natural Language, although it can be used to do so.

Natural Languages are produced using “Linear Context-Free Rewriting Systems,” a less effective variation of Context Sensitive Grammar.

In order to solve the choice problem in a reasonable amount of time, research in computational linguistics focuses on creating classes of languages that are stronger than Context Free but weaker than Context Sensitive. As a result, numerous grammars have been developed, including Range Concatenation Grammar, Tree Adjoining Grammar, Combinatory Categorial Grammar, and others.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.

Also Explore,