Convert the following context-free grammar into GNF: S \to XY X \to YS

Back to the 2019 paper

Module 2: Context-free languages and pushdown automata

20197m

Convert the following context-free grammar into GNF:
$S \to XY$
$X \to YS \mid b$
$Y \to SX \mid a$

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYConvert the CFG to GNF: S \to AB \mid BC \\ A \to aB \mid bA \mid a \\ B \to bB \mid cC \mid b \\ C \to c20227m Formal Language & Automata TheoryBegin with the grammar: S \to ASB / \epsilon A \to aAS / a B \to SbS / A / bb (i) Eliminate \epsilon-productions. (ii) Eliminate unit productions in the resulting grammar. (iii) Eliminate any useless symbol in the resulting grammar. (iv) Put the resulting grammar into CNF.202214m FORMAL LANGUAGE & AUTOMATA THEORYShow that the following grammar is ambiguous: S \rightarrow SS | aSb | bSa | \epsilon20257m FORMAL LANGUAGE & AUTOMATA THEORYConstruct NPDA for the grammar: S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A20237m

PreviousConsider the following language: L = \{a^m b^{2n} c^{3n} d^p \mid p > m \text{ and } m, n \ge 1\} Write a context-free grammar to generate L and write shortest string in L.NextConstruct a push-down automata that accepts the following language: L = \{uawb \mid u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.

Try Coursify Free