## Context-free grammar for language involving multiplication

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.

Posted on Categories proxies

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

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?

Posted on Categories proxies

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

Posted on Categories proxies

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

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 ?

Posted on Categories proxies

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

Posted on Categories proxies

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

Posted on Categories proxies

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

Posted on Categories proxies

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

Posted on Categories proxies

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

Posted on Categories proxies