Practice Theory of Computation - GATE - CSIT, DSAI & Interview Preparation Offered by Unacademy

Theory of Computation

Which is the correct CFG for this language: $\mathrm{a^{n} b^{m} c^{n} d^{m}}$ where n ,m >=1?

$\mathrm{S} \rightarrow \mathrm{A B}$

$\mathrm{A} \rightarrow \mathrm{a A b} / \mathrm{a b}$

$\mathrm{B} \rightarrow \mathrm{b B c} / \mathrm{b c}$

$\mathrm{S} \rightarrow \mathrm{aSc} / \mathrm{aAc}$

$\mathrm{A} \rightarrow \mathrm{a A b} \mathrm{ /ab }$

None

$\mathrm{S} \rightarrow \mathrm{aSd} / \mathrm{aAd}$

$\mathrm{A} \rightarrow \mathrm{bAc} / \mathrm{bc}$