## How to determine if a language is deterministic context-free language?

I have the following question to solve : DCFL means Deterministic Context-Free Language

I tried to find a counter example to the problem, however I didn’t find anything. So I am thinking that it is deterministic. I am wondering how do I approach these kind of questions? and how to determine a language is deterministic ?

## Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

• $$S \rightarrow aSb\;|\;\epsilon$$
• $$S \rightarrow aSbS\;|\;\epsilon$$
• $$S \rightarrow aSaSb\;|\;\epsilon$$
• $$S \rightarrow aaSaaSbb\;|\;\epsilon$$
• $$S \rightarrow aSbScSdSeSf\;|\;\epsilon$$
• etc…

Grammars like these uphold 4 basic rules:

1. The non-terminal symbol $$S$$ can never appear next to itself.
• e.g. $$[\;S \rightarrow aSSb\;|\;\epsilon\;]$$ would not be allowed.
2. The non-terminal symbol $$S$$ can appear at the beginning or end of a production but not on both sides at the same time.
• e.g. $$[\;S \rightarrow SabaS\;|\;\epsilon\;]$$ would not be allowed.
• e.g. $$[\;S \rightarrow Saba\;|\;\epsilon\;]$$ or $$[\;S \rightarrow abaS\;|\;\epsilon\;]$$ would be allowed.
3. The sequence of terminal symbols that exist between each non-terminal $$S$$ cannot all match.
• e.g. $$[\;S \rightarrow aSaSa\;|\;\epsilon\;]$$, $$[\;S \rightarrow abSabSab\;|\;\epsilon\;]$$, etc. would not be allowed.
• e.g. $$[\;S \rightarrow aSaSb\;|\;\epsilon\;]$$, $$[\;S \rightarrow abSabSaf\;|\;\epsilon\;]$$, etc. would be allowed.
4. The sequence of terminal symbols at the beginning and end cannot match.
(i.e. $$[\;S \rightarrow ☐_1SaS☐_2\;|\;\epsilon\;]$$ s.t. $$☐_1 \neq ☐_2$$ where $$☐_1$$ and $$☐_2$$ are a sequence of terminal symbols)
• e.g. $$[\;S \rightarrow aSbSa\;|\;\epsilon\;]$$, $$[\;S \rightarrow aaSbSaaS\;|\;\epsilon\;]$$, etc. would not be allowed.
• e.g. $$[\;S \rightarrow aSbSb\;|\;\epsilon\;]$$, $$[\;S \rightarrow aaSbSaxS\;|\;\epsilon\;]$$, etc. would be allowed.

Are (Context-Free) Grammars, that follow these 4 rules, always unambiguous? It would seem so. I really don’t see any conceivable way that such Grammars could be ambiguous.

(Note: To show why Rule 4 is necessary consider the grammar $$S \rightarrow aSbSa\;|\;\epsilon$$ with the string $$aababaababaa$$. A visual derivation can be found here.)

I’ve spent a lot of time thinking about this question and have had a hard time finding any way of either proving or disproving it. I’ve tried showing that Grammars like these are $$LL(1)$$. However, it seems only Grammars of the form $$S \rightarrow aSb\;|\;\epsilon$$ are $$LL(1)$$. Grammars like $$S \rightarrow aSaSb\;|\;\epsilon$$ are not $$LL(1)$$. Maybe I need to use a higher $$k$$ for $$LL(k)$$?

(This question is a follow-up/reformulation of a previous question.)

I would really appreciate any help I could get here.

## How do I calculate the Nth result of a context-free grammar?

Given a context-free grammar and a maximum depth, how do I directly find the Nth result without calculating or caching intermediary results?

## Are Context-Free Grammars with only one Production Rule always Unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

• $$S \rightarrow aSb\space|\space\epsilon$$
• $$S \rightarrow aSSb\space|\space\epsilon$$
• $$S \rightarrow aSbS\space|\space\epsilon$$
• $$S \rightarrow aSaSb\space|\space\epsilon$$
• $$S \rightarrow aaSaaSbb\space|\space\epsilon$$
• $$S \rightarrow aSbScSdSeSf\space|\space\epsilon$$
• $$S \rightarrow aSSbcSd\space|\space\epsilon$$
• etc…

Are all these Grammars unambiguous? Will every Grammar with only one production rule (not including the epsilon production) always be unambiguous? It would seem so, but I’m not totally sure.

Grammars that only contain one unique terminal symbol could be ambiguous. (ex. $$S\rightarrow aSaSa\space|\space\epsilon$$) However, Grammars with at least two distinct terminal symbols seem like they should always be unambiguous.

I’ve tried showing that Grammars like these are $$LL(1)$$. However, it seems only Grammars of the form $$S \rightarrow aSb\space|\space\epsilon$$ are $$LL(1)$$. Grammars like $$S \rightarrow aSaSb\space|\space\epsilon$$ are not $$LL(1)$$. (Illustrated in the parse table below.)

Despite the example Grammar above not being $$LL(1)$$, it still seems to be unambiguous. Maybe it’s simply a matter of using a higher $$k$$ for $$LL(k)$$?

In short, are (Context-Free) Grammars with only one production rule (not including the epsilon production) and at least two unique terminal symbols always unambiguous?

I would really love some help, any at all would be greatly appreciated.

## How to find a context-free grammar from a difficult language?

Some Languages are trivial to find their respective context-free grammar. Like for example $$L= \{a^nb^n: n \geqslant 0\}$$. However some are really difficult to solve. I would like to have some advice on how I can tackle them.

For example I have the following language that I have been trying to solve for a while :

I tried to divide the problem into three cases as follow:

case i: na $$\le$$ nb

case ii: nb $$\le$$ na $$<$$ 2nb

case iii: na $$\ge$$ 2nb

The first case was easy to solve however I am stuck in case ii. At this point I don’t even know if the procedure that I chose is the correct one.

## Context-free grammar how to have same number of variables within a language

I am trying to get a CFG for the language:

the set A of odd-length strings in {a,b}^* whose first, middle and last symbols are all the same 

(some example of correct answers would be: a, aaa, ababa, aababba, some incorrect answers include: ɛ, aaaa, abbaa)

This is what I’ve done so far:

S=a|b|aTaTa|bTbTb T=aT|bT|ɛ 

However the problem is, I need T to be a string of any combination of ‘a’s and ‘b’s but of the same length, but I’m not sure how to express this. As you can see above, I can get strings made up of any combination, but they won’t be the same length when passed to S. Any help is appreciated!

## Context-free grammar how to have unequal number of a on either side of a b

I have been trying to create a CFG for the set

{w=(a^i)b(a^j)|where i =/= j} 

To my understanding, there are essentially 2 scenarios, one where there are more ‘a’s on the left side of ‘b’, and one where there are more ‘a’s on the right side of ‘b’. So far I have come up with:

S = TbR | RbT T = aT | ε R = TaT 

My intention is the have R to always have more ‘a’s than T, however I don’t think this is correct as T can be greater than R in this definition, as R could take be just ‘a’ while T is ‘aa’. I need a bit of help defining 2 variables T and R, where R always has more ‘a’s than T.

## Context-free grammar of the concatenation of a string S and subsequence of reversed S

I have to find a Context-Free grammar that generates the language:

$$L_1 = \{x\#y\ |\ y$$ is a subsequence of $$x^R$$, and $$x\in\{a,b\}^*\}$$, $$\Sigma=\{a,b,\#\}$$

The concatenation of two mutually reversed strings are pretty simple, but I just can’t figure out how to express “plugging in random terminals in $$x$$” so that $$x^R$$ could contain $$y$$ as its subsequence.

## Motivation

Consider the following languages, are they context-free?

• $$\{x \# y: x \neq y\}$$
• $$\{x y: |x|=|y|, x \neq y\}$$
• $$\{x \# y: |x|=|y|, x \neq y\}$$
• $$\{x y: |x|=|y|,d(x,y)>1\}$$

The first three are explained here, the last one is this question.

I’m wondering whether there is an algorithm to solve this kind of problem in general.

## Question

Given two strings $$x,y$$, let $$\operatorname{zip}(x,y)$$ denote the string $$(x_1,y_1)(x_2,y_2)\dots(x_n,y_n)$$. Note that letters in $$\operatorname{zip}(x,y)$$ are pairs. If one string is shorter, we pad it with an extra blank symbol.

Is the following problem decidable?

Given a regular language $$L$$, is $$\{x y: \operatorname{zip}(x,y) \in L\}$$ context-free?

If the answer is positive, we can solve the four problems from the motivation section by picking a suitable $$L$$.