# Tag Info

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