3
votes
3answers
62 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
0
votes
0answers
99 views

Chomsky Normal Form solution for a problem

Here is my attempt at CNF, Original: $$ \begin{align*} S &\to 1 A \mid O B \\ A &\to O B O \mid 1 0 \mid \epsilon \\ B &\to A 1 A \mid 0 1 \end{align*} $$ CNF: $$ \begin{align*} S ...
2
votes
1answer
3k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
1answer
119 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
2
votes
1answer
216 views

Proving a language is regular or irregular

I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to ...