3
Your language is very similar to the Dyck language, the only difference being that the Dyck language usually contains the empty string.
Here is an unambiguous grammar for your language:
$$
S \to (S)S \mid (S) \mid ()S \mid()
$$
In order to check that it generates the correct language, and unambiguously, let us consider a slightly different description of ...
2
We want to generate strings of the form $1^n 0^m 1^k 0^p$ with the same number of $0$ and $1$. This language can be generated by distinguishing two cases.
The first approach is to draw a diagram what happens if we keep counting the difference between the numbers of $0$ and $1$. This difference between the cases is whether the count drops below zero or not.
...
2
TMs accept words as input.
What this paragraph is saying is that you cannot encode arbitrary languages as finite strings (aka words), and hence you cannot easily describe a property over languages themselves (for instance, a property of "all languages that contain the empty word", is a property over languages).
Afterwards it represents a way to ...
1
Yes, there are. There is an algorithm that, given any PDA $P$ and any input word $x$, directly checks whether $x$ is accepted by $P$, without first converting $P$ to a CFG. The algorithm takes running time $O(n^3)$ (treating the size of $P$ as a constant that is absorbed into the big-O notation).
The idea is that, given a PDA $P$, we can compute a ...
1
No, because the idea is wrong (or at very least, too vague and imprecise to be useful in its current form). As Yuval Filmus hints, the language $\{a^n b^n \mid n \in \mathbb{N}\}$ appears to have "global structure", yet is context-free.
1
Admittedly, the sentence you give is indeed a trifle obscure. Simply said, it is saying that if we have a property of a language, like "any string in the language has odd length", we can't hope to recognize the property by using a TM that will iterate over all strings of all possible languages to test, since that would clearly be an infinite input, ...
Only top voted, non community-wiki answers of a minimum length are eligible