The Gateway to Computer Science Excellence
+1 vote
216 views
Construct context-free grammars to accept the following languages.

$$\begin{align*} \large L = \left \{ 0^i1^j2^k \;\; | \;\; i \neq j \;\; or \;\; j \neq k \right \} \end{align*}$$
in Theory of Computation by Junior (517 points)
retagged by | 216 views

1 Answer

+3 votes
Best answer
$$\begin{align*} &S\rightarrow S_1 \;\; | \;\; S_2 \\ \\ &S_1 \rightarrow ABD \;\; | \;\; CAD \\ \\ &A \rightarrow 0A1 \;\; | \;\; \epsilon \\ \\ &B \rightarrow 1B \;\; | \;\; 1 \\ &C \rightarrow 0C \;\; | \;\; 0 \\ &D \rightarrow 2D \;\; | \;\; \epsilon \\ \\ &S_2 \rightarrow GEF \;\; | \;\; GBE \\ \\ &E \rightarrow 1E2 \;\; | \;\; \epsilon \\ &F \rightarrow 2F \;\; | \;\; 2 \\ &G \rightarrow 0G \;\; | \;\; \epsilon \\ \end{align*}$$
by Veteran (57k points)
selected by
0
thnq debashish da
0
how to write it for L = {0^i1^j2^k : I != j and j!=k}

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,542 answers
195,693 comments
101,537 users