Extension for CFG, what is it?

Question

Consider the following extension for context-free grammars, which allows rules to have on the left side one (or more) terminals on the right side of the nonterminal. That is, the rules of the form:

A b -> ... 

The right side can be anything, for example, in context-free grammars. In particular, it is not required that the right side will have exactly the same trailing character at the end. In this case, this extension will be context sensitive. But a terminal is not just a context. This terminal is sometimes called a pushback.

Clearly, this is no longer CFG (type-2). It includes type 1. But what is it? Is type-0 already?

This particular extension is allowed in the "Specific Phrase" dcg columns in the Prolog. (To avoid misunderstandings, I do not consider the full Prolog extensions here. That is, I assume that the terminals come from a finite alphabet and are not arbitrary terms, nor do I consider the additional Prolog arguments that are allowed in DCG, 0 already.)

---

Edit: Here is a simpler way to describe the extension: Add form to CFG rules

 A b -> <epsilon> 

Answer 1

To answer my question regarding the Prolog DCG formalism, this extension is now called semicontext . See N253 DIN Draft for DCG 2014-04-08 - ISO / IEC WDTR 13211-3: 2014-04-08

Considering

 a1, [b] --> ... . a2, [b,b] --> ... . 

The terminal sequence [b] now a semi-context, as well as the terminal sequence [b,b] .

Whether the same final sequence will now appear at the end of the rule, we will have a context:

 a3, [b,b] --> ..., [b,b]. 

So, “semi” here means “half” - similar to a semigroup where half the algebraic properties of the group are satisfied.

Answer 2

Here is a partial answer:

The grammar is inside type 0. A context-sensitive grammar (type-1) has rules of the form wAx -> wBx , where w and x are strings of terminals and non-terminals, and B is not empty. Note that since B is not empty, |wAx| <= |wBx| |wAx| <= |wBx| . Your grammar has rules of the form Ax -> z , where z is a string of terminals and non-terminals and can be empty, and x can be deleted. This violates two principles of the CWG.

Unsatisfactory, I did not answer two things:

• Is the language created by your type 1 grammar? The grammar is of type-0, but this does not mean that the language cannot be of type-1. For example, ordinary languages ​​(type-3) can be described by CFG (type-2).

• Is the language recursive ? This is important because, if so, the language is solvable (does not suffer from a problem with stopping).

  I am currently trying to make proof for the second point, but it is probably not in my power.

Answer 3

Yes, this is type 0, I think. The principle for the first 3 types (3, 2 and 1) is that they cannot perform the reduction. These are generic types only.

Here you can convert the terminal to epsilon so that it prints 0.