last day (15 days later) » 

Feeds
Feeds
15:15
3
A: Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Yuval FilmusHere is the idea in a nutshell: Given a Turing machine $M$, we can construct a context-free grammar $G$ such that if $M$ halts then $\overline{L(G)} = \{t\}$, where $t$ is the transcript of the halting computation of $M$, and if $M$ doesn't halt then $\overline{L(G)} = \emptyset$. Consequently,...

Closure
Closure
Why determining whether $L(G) = \emptyset$ or whether $L(G)$ is finite is undecidable even for "deterministic context-sensitive languages?
Yuval Filmus
Yuval Filmus
Since the LBA which checks the validity of an input transcript is deterministic.
Closure
Closure
That understand. But why $L(G) = \emptyset$ and $L(G)=$ finite is undecidable?
Yuval Filmus
Yuval Filmus
If you could decide these problems, you could decide the halting problem, which we know is undecidable.
Closure
Closure
What is transcript, encoding of TM?
Yuval Filmus
Yuval Filmus
15:15
It's a sequence of configurations recording the execution of the machine.
Closure
Closure
illegal" transcripts means?
Yuval Filmus
Yuval Filmus
You'll have to consult the full proof for that.
Closure
Closure
I don't want any proof. I want just what is it. As per my understanding it has illegal state and head location etc. Am I correct?
Yuval Filmus
Yuval Filmus
It is a string which does not represent a valid transcript.
Closure
Closure
Here you consider $L(G)$ is transcript or language?
Yuval Filmus
Yuval Filmus
15:15
A transcript is a string. A language is a collection of strings.
Closure
Closure
means $L(G)$ is collection transcript?
Yuval Filmus
Yuval Filmus
The language $L(G)$ in the second bullet is either empty, or contains a single string.
Closure
Closure
Why $\overline{L(G)} = \{t\}$ isn't single string for first bullet?
Yuval Filmus
Yuval Filmus
The role that $L(G)$ plays in the second bullet is identical to the role that $\overline{L(G)}$ plays in the first bullet.
I'm sorry, I don't understand this comment.
Closure
Closure
I mean $\overline{L(G)} = \{t\}$ isn't single string because complement of cfl isn't closed, it maybe regular, csl etc. That's why it's content also more than one. Am I right?
Yuval Filmus
Yuval Filmus
15:15
The context-free grammar $G$ is defined to satisfy the properties in the first bullet.
Closure
Closure
Yes, first bullet is cfl. But what is the reason behind $\{t\}$ has more than one string?
Yuval Filmus
Yuval Filmus
The set $\{t\}$ only contains one string.
Closure
Closure
Both bulletin {t} is unit set?
Yuval Filmus
Yuval Filmus
The notation "$\{t\}$" has only one meaning: the set consisting of a single element, $t$.
Closure
Closure
complement of cfl is illegal transcript because it's not closed under complement?
Yuval Filmus
Yuval Filmus
15:15
I'm sorry, you'll have to look at the proof. I won't answer any more questions.
Closure
Closure
it's my final question believe me. I have understood everything. Please just tell in one line.
Yuval Filmus
Yuval Filmus
Unfortunately I am unable to understand your question.
Closure
Closure
complement of cfl is illegal transcript because it's not closed under complement?
Yuval Filmus
Yuval Filmus
No, that's not the reason. For the reason, you'll need to take a look at the proof. There's only so much that you can understand "intuitively" without ever looking at any kind of detail.

last day (15 days later) »