The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

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