Recent questions tagged difficult

A $\text{queue automaton}$ is an automaton in which the temporary storage is a queue. Assume that such a machine is an online machine, that is, it has no input file, with...

A counter is a stack with an alphabet of exactly two symbols a stack start symbol and a counter symbol. Only the counter symbol can be put on the stack or removed from it...

Find context-sensitive grammars for the following languages.$(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$.$(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.

Find the context-sensitive grammars for the following languages.$\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$.$\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$.$\text{(c)}...

Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation ...

$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in The...

Show that for arbitrary context-free grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is context-free$”$ is undecidable.

Show that the problem of determining whether or not $L(G_1) \subseteq L(G_2)$ is undecidable for context-free grammars $G_1,\space G_2$.

Each inhabitant of a remote village always tells the truth or always lies. A villager will give only a “Yes” or a “No” response to a question a tourist asks. Suppose you ...

A stage of an $n \times n$ banyan network consists of $(n/2) 2 \times 2$ switching elements. The first stage directs packets to the correct half of the network, the next ...

Coaxial cable Ethernet was limited to a maximum of $500$m between repeaters, which regenerate the signal to $100$% of its original amplitude. Along one $500$-m segment, t...

With $1$ parity bit we can detect all $1$-bit errors. Show that at least one generalization fails, as follows:(b) Find an $N$ (not necessarily minimal) such that no $32$-...