## GATE CSE 2018, Which of the following languages are context-free?

A] {ambncpdq | m+p = n+q, where m, n, p, q >=0}

B] {ambncpdq | m = n and p = q, where m, n, p, q >=0}

C] {ambncpdq | m = n = p and p not= q, where m, n, p, q >=0}

D] {ambncpdq | mn = p+q, where m, n, p, q >=0}

Instead of Formal proofs if any answer can provide telltale signs of a language being CFL or not will be more appreciated, because this question is taken from a competitive exam. Formal proofs are welcome too.

Here is my approach

A] I don’t have any idea for constructing PDA for this language, probably not a CFL. Also by pumping lemma splitting the word in ‘uvwxy’ for any ‘vwx’ (belonging to ‘akbk‘ and such combinations), the equality won’t hold. Thus not a CFL.

B] Is a CFL we can push a’s and pop on b’s, same for c’s and d’s.

C] Not a CFL, as we need two stacks, one for keeping count of |a|==|b| and second for |b|==|c|.

D] Not a CFL, cause we can’t construct a PDA, such a PDA will require capability to move back and forth on input string (for keeping track of m*n), which is not possible.

## Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task.
And i understand following procedure:

$$S→aA | aB$$
Becomes:
$$S→aS’$$
$$S’→A|B$$

Yet I’m running into problems with this particular grammar:

$$S→AD|bbS|bScS|BS$$
$$A→aAbb | abb$$
$$B→aB|ba|b$$
$$D→cDd|cccd$$

How to remove left factoring from it, I’m trying to convert it into LL(1) grammar

## How to show that language L is NOT context-free?

True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free.

I know that you can prove closure under context-free languages using union, but does the above work, too? Any help you can provide would be greatly appreciated!

## Pumping lemma for regular languages vs. Pumping lemma for context-free languages

How can I prove the next claim:

If a language $$L$$ meets the pumping lemma for regular languages then $$L$$ meets the pumping lemma for context-free languages?

(Without any pre-condition about the regularity of $$L$$)

## context-free language : if yx belongs to cfl then xy is also cfl

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language.

C is a Context-Free Language.

I think we can use the PDA defining C and edit final states.

Any ideas? thank you.

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

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

## Context-free Grammar Exercise

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

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

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.