Theory Of Computation (2160704)

BE | Semester-7   Winter-2018 | 27/11/2018

Q3) (a)

Define Context-Sensitive Grammar. What is the language of following context-sensitive grammar?

Type 1 grammar (Context Sensitive Grammar)

  • Their productions are of the form:
    αAβ -> απβ
    where A is non terminal and α, β, π are strings of terminals and non terminals.
  • The strings α and β may be empty, but π must be non-empty.
  • Here, a string π can be replaced by 'A' (or vice versa) only when it is enclosed by the strings α and β in a sentential form.
  • Example: AB -> AbBc
  • A -> bcA
  • B -> b