New answers tagged computation-models
1
I slept on it and remembered there was another wording issue that was bugging me: "generates an equivalence relation". I wasn't familiar with it and assumed it just meant "is an equivalence relation". Turns out I was wrong. It has a very specific meaning that Wikipedia describes thusly:
Given any binary relation $A \subset X \times X$ on $X$, the ...
0
From your figure, assume the orange is $x_1=mx_2+n$, then substituting point $(5,5)$ or $(9,1)$ will give you: $x_2=-x_1+10$. Similarly, you can know that the blue line is $x_2=-x_1+7$. Then the dotted line in the middle (which is exactly the separating hyperplane) is
\begin{align}
&x_2=\frac12((-x_1+10)+(x_2=-x_1+7))=x_2=-x_1+8.5\\
\Longrightarrow\;
&...
2
You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.
So. We have some DFA $M$, and we can build a PDA $N$ which ...
Top 50 recent answers are included
