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

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.

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

I have the following question to solve : DCFL means Deterministic Context-Free Languageenter image description here

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 ?