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.)

enter image description here

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 :enter image description here

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.

Is it decidable if this zipping operation gives a context-free language?


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$ .

proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular [duplicate]

This question already has an answer here:

  • First half of context-free palindromes 3 answers

I am trying to prove this following theorem, can someone help please?

Let $ L$ be a language over the alphabet $ \Sigma = \{ a,b \}$ . If $ L’ = \{ w$ w^R \mid w \in L\}$ is context-free, then $ L$ is regular.

Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

I’m having trouble with this particular language: $ $ \{a^i b^j c^k \mid i+j \le k\}$ $

If it’s not context-free, I don’t know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I don’t know how to create a context-free grammar that generates this language.

Which one applies? Can you help me out?

A context-free grammar for all strings that end in b and have an even number of bs

I’m trying to find CFG’s that generate a regular language over the alphabet {a b}

I believe I got this one right: All strings that end in b and have an even number of b’s in total:

$ \qquad S \to SS \ \qquad S \to YbYb \mid \varepsilon \ \qquad Y \to aY \mid \varepsilon$

However, Im not sure how to accomplish this with an odd number of b‘s.

So for example, how could I find a CFG that generates all strings that end in b and have an odd number of b’s in total: So far I have this,

$ \qquad S \to SS \ \qquad S \to YYb \mid \varepsilon \ \qquad Y \to abY \mid baY \mid \varepsilon$

But this can generate abababb so it’s incorrect and Im stumped at this point.

Is the language $L_1$ a context-free language?

Is the language $ L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language?

It certainly isn’t regular, but is it context free?

I’m having trouble creating a grammar that creates terminal symbols from the outside-in; Is there anything to look for explicitly that tells me it is/isn’t CF?

And if it was in fact context-free, how would I go about proving that?

Thank you