4

I am interested in generating elements of a context sensitive language as described by Chomsky, as described in Chomsky Classification of Grammars under the section "Type - 1 Grammar".

(Basically, similar to a standard context-free grammar, but allowing multiple symbols on the left side of a production rule, including terminals).

I know about definite clause grammars in Prolog, but I don't see an obvious mapping between those and Chomsky's context sensitive languages. Is there a "universal" way to use the DCG framework to describe production rules with multiple symbols on the left side, or do I need an ad hoc approach for each individual language?

false
  • 10,264
  • 13
  • 101
  • 209
lightning
  • 389
  • 1
  • 9
  • 6
    There is an example of how to do this on [Wikipedia](https://en.wikipedia.org/wiki/Definite_clause_grammar#Non-context-free_grammars) of all places, but for this to be a legitimate question on S.O., you have to have a concrete problem you're trying to solve. – Daniel Lyons Feb 01 '19 at 18:08
  • 1
    Of interest: [Chomsky hierarchy](https://en.wikipedia.org/wiki/Chomsky_hierarchy) - Type 1 - Production rules - αAβ → αγβ – Guy Coder Feb 02 '19 at 10:25

1 Answers1

2

Context on the right-hand side can be encoded directly using a semicontext:

nt1, "context" --> nt2, "context".

For context on the left-hand side, there is no obvious direct encoding. Most often arguments to the non-terminals are used.

false
  • 10,264
  • 13
  • 101
  • 209