This is my Homework problem. Can someone please help me out! Find CFG(Context Free Grammar) for the language L={$a^ib^jc^k | i\neq j\ or\ j\neq k$}.
Asked
Active
Viewed 1,913 times
1
-
You should post the question about finding the FSA in a separate thread. – zarathustra Aug 16 '14 at 10:28
1 Answers
2
Hint: (for the grammar.) The language $L$ is the union of $\{a^ib^jc^k \mid i<j\}$, $\{a^ib^jc^j \mid i>j\}$, $\{a^ib^jc^k\mid j>k\}$, and $\{a^ib^jc^k\mid j<k\}$. If you find grammars for the four previous languages, there exists a grammar for $L$ since context-free languages are closed under union.
zarathustra
- 4,891
-
Actually I had already realized this fact. What I want is that can I implement the union without using epsilon-transitions. Can you help me in that matter! – Madhusudana Aug 17 '14 at 11:45
-
@Hitarth: why are you talking about $\epsilon$-transitions? When dealing with grammars, closure under union is given by a production rule $N\rightarrow A\mid B$ where $A$ and $B$ are non-terminals that generate the desired languages. – zarathustra Aug 18 '14 at 11:52