I’m struggling to find the context-free grammar for the following language: $ $ L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\} $ $ Any help would be appreciated.

# Tag: Contextfree

## Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $ L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I’ve tried the following:

$ G=(V,\Sigma,R,S)$ with $ \Sigma=\{a,b,c,\lambda\}$ , $ V=\{S,B\}$ , $ S=S$ and $ $ R=\{S\to \lambda\mid aSc\mid B,\;B\to bBc\mid \lambda\},$ $ which would output $ L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ , in my opinion. I’ve tried to test my grammar by applying the rules in different combinations and I didn’t spot any error yet.

*So I’m asking myself:*

Is there a way to to see if $ L(G)=L$ or do I need to assume, that I’ve done everything correctly after testing some cases?

## Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{equation}

I already know that \begin{equation} \Sigma=\{a, b, c\} \end{equation} and V (non terminal symbols) maybe have to be \begin{equation} V=\{S, A, B, C\} \end{equation}

Thank you for helping.

## Context-free or not: number of w not same

Is the following a context-free language? L = {a_concate_n_w_w_concate_R_a_concate_n | n ≥ 0, w ∈ {a, b}*} or L = {a^n w w^R a^n |…….}

I think no because the number of w’s is not equal.

Somebody please guide me.

Zulfi.

## 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:

**The non-terminal symbol $ S$ can never appear next to itself.**- e.g. $ [\;S \rightarrow aSSb\;|\;\epsilon\;]$ would
**not**be allowed.

- e.g. $ [\;S \rightarrow aSSb\;|\;\epsilon\;]$ would
**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.

- e.g. $ [\;S \rightarrow SabaS\;|\;\epsilon\;]$ would
**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.

- e.g. $ [\;S \rightarrow aSaSa\;|\;\epsilon\;]$ , $ [\;S \rightarrow abSabSab\;|\;\epsilon\;]$ , etc. would
**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.

- e.g. $ [\;S \rightarrow aSbSa\;|\;\epsilon\;]$ , $ [\;S \rightarrow aaSbSaaS\;|\;\epsilon\;]$ , etc. would

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

**distinct terminal symbols seem like they should always be unambiguous.**

*two*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: n_{a} $ \le$ n_{b}

case ii: n_{b} $ \le$ n_{a} $ <$ 2n_{b}

case iii: n_{a} $ \ge$ 2n_{b}

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!