0
$\begingroup$

I have to find a CFG for the given expression:

$L = \{a^wb^xc^yd^z | w + x = y + z\}$

This is what I've tried so far:

S -> aSd | B | ϵ

B -> bBc | ϵ

It works for expressions like: aabcdd, abbbcccd

However, using my grammar I wouldn'd be able to generate strings like: aaaacddd, abbddd, which, I assume, the language L should contain.

$\endgroup$
2
  • $\begingroup$ If you try hard enough, you will be able to solve this on your own. $\endgroup$ Jun 17 at 10:32
  • $\begingroup$ As @YuvalFilmus said, this question is very easy, just try to think about it in a more logical way. For each $a$ you see insert $0$ to the stack, for each $b$ you see insert $0$ to the stack, for each $c$ you see remove $0$ from the stack and for each $d$ you see remove $0$ from the stack. It's more simple to build a PDA for this language, it's overall 4 states and more understandable. $\endgroup$
    – Mohamad S.
    Jun 17 at 13:08

3 Answers 3

3
$\begingroup$

The constraints on $w, x,y, z$ are not given, I choose everyone $\geq 0.$

The strings could be equal $a$ and equal $d,$ equal $b$ and equal $c,$ equal $b$ and equal $d,$ equal $a$ and equal $c $ etc(since $w, x,y, z\geq 0.$)

$S\to aSd. $

$X\to aXc. $

$Y\to bYd. $

$Z\to bZc. $

Now from start symbol we could go either $X, Y \text{or} Z$ directly. Then $S$ becomes now $S\to aSd/X/Y/Z.$

Now for $X$ when are generating $a, c$ we are generating $b, c$ in middle, but $b, c$ are generated by $Z.$ So $X$ becomes $X\to aXc/Z.$

Same things happens with $Y$, So $Y$ becomes $Y\to bYd/Z.$

Now collectively all things together,

$S\to aSd/X/Y/Z.$

$X\to aXc/Z.$

$Y\to bYd/Z.$

$Z\to bZc/\epsilon$

Note:- For $w, x,y, z\geq 1,$

$S\to aSd/aXd/aYd/aZd.$

$X\to aXc/Z.$

$Y\to bYd/Z.$

$Z\to bZc/bc$

$\endgroup$
1
$\begingroup$

This answer on purpose is more complicated than necessary. My goal is to apply a general property of regular and context-free languages, see: Prove that the equal-length concatenation of regular languages is context free.

Given regular languages $A$ and $B$, then $A@B=\{xy\mid x\in A, y\in B \text{ and } |x|=|y|\}$ is context free.

The solution is to generate $A$ with a right-linear grammar, and to generate $B$, this time backwards, with a left-linear grammar. Then the two derivations can be synchronized, which ensures the equal length requirement. The new grammar is in fact linear, a subclass of the context-free grammars.

In this example we choose the following two grammars for $A =a^*b^*$ and $B = c^*d^*$, with axioms $S$ and $X$ respectively.

$S \to \varepsilon \mid aS \mid bT$, $T\to \varepsilon \mid bT$

$X \to \varepsilon \mid Xd \mid Yc$, $Y\to \varepsilon \mid Yc$

Synchronize the two grammars, using pairs of nonterminals (which form a new alphabet of nonterminals). For each of the sides we apply its possible productions from the original right/left linear grammar.

$\langle SX \rangle \to \varepsilon \mid a\langle SX\rangle d \mid a \langle SY\rangle c\mid b\langle TX\rangle d \mid b \langle TY\rangle c$

$\langle SY \rangle \to \varepsilon \mid a\langle SY\rangle c \mid b \langle TY\rangle c$

$\langle TX \rangle \to \varepsilon \mid b\langle TX\rangle d \mid b \langle TY\rangle c$

$\langle TY \rangle \to \varepsilon \mid b\langle TY\rangle c$

Renaming the four nonterminals into $S,P,Q,R$ we obtain a more familiar solution.

$S \to \varepsilon \mid aS d \mid a P c\mid bQ d \mid b R c$

$P \to \varepsilon \mid aP c \mid b R c$

$Q \to \varepsilon \mid bQ d \mid b R c$

$R \to \varepsilon \mid bR c$

$\endgroup$
0
$\begingroup$

You have a grammar where it is natural to build sentences from the outside to the inside. You'll have a symbol in the middle, and in each derivation step you add a terminal at the left and one at the right, so the number of symbols on the left and on the right are the same.

Initially you produce a's and d's. Then you switch either to a's and c's or to b's and d's, from there to b's and c's, and eventually you stop producing new letters. So here's the grammar:

S -> aSd | T | U
T -> bTd | V
U -> aUc | V
V -> bVc | eps
$\endgroup$
2
  • $\begingroup$ That's the same thing I do.what's new? $\endgroup$ Jun 20 at 14:15
  • $\begingroup$ Look at all the unnecessary stuff that is missing. And it's written in English. $\endgroup$
    – gnasher729
    Jun 21 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.