Construct a CFG for: \{ 0^i 1^j 2^k \mid i + j \ge 2k \} — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2022 paper

Module 2: Context-Free Languages (CFL) and PDA

20227m

Construct a CFG for:

$\{ 0^i 1^j 2^k \mid i + j \ge 2k \}$

Search Google Ask AI

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYConstruct a PDA for the language: L = \{ 0^m 1^n 0^k \mid k \ge 1, m \ge 1, m > n + 2 \}20247m Formal Language & Automata TheoryConstruct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.20217m FORMAL LANGUAGE & AUTOMATA THEORYConstruct an NFA accepting strings over \{0,1,2\} beginning with 0, followed by an odd number of 1s, ending with any number of 2s.20217m FORMAL LANGUAGE & AUTOMATA THEORYDesign a context-free grammar (CFG) that generates all palindromes over the alphabet {0, 1}. The grammar should generate both even-length palindromes (e.g., 0110) and odd-length palindromes (e.g., 010).20257m

PreviousShow that the language of palindromes over \{a, b\} is not regular.NextConvert 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 c