chomsky-hierarchy

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which of the following is/are TRUE...

Consider the languages $${L_1}$$, $${L_2}$$ and $${L_3}$$ are given below. $$$\eqalign{ & {L_1} = \left\{ {{0^p}{1^q}\left| {p,q \in N} \right.} \right\} \cr & {L_2} = \left\{ {{0^...

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, language. Which one of the follow...

The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is

Consider the grammar with the following productions. $$S \to a\,\alpha \,\,b\left| {\,\,b\,\alpha } \right.\,c\,\left| {aB} \right.$$ $$S \to \alpha S\,\left| b \right.$$ $$S \to \...

Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ? $$

Which of the following problems are un-decidable?