# Tag Info

## New answers tagged automata

0

Let $A$ be the alphabet and let $B = \{[a_1a_2] \mid a_1, a_2 \in A \}$. Let $\alpha, \beta: B^* \to A^*$ be the monoid homomorphisms defined by $\alpha([a_1a_2]) = a_1a_2$ and $\beta([a_1a_2]) = a_2a_1$, for each letter $[a_1a_2]$ of $B$. Now $L' = \beta(\alpha^{-1}(L))$. Since regular languages are closed under homomorphisms and inverses of homomorphisms, ...

0

How about $S \rightarrow aSA \mid bS \mid \varepsilon$ and $A \rightarrow b \mid aA \mid \varepsilon$? Disclaimer: I didn't think about this for more than ten seconds, so please check!

0

p-regular languages are commonly known as (regular) group languages in the literature since their syntactic monoid is a finite group. If a language is accepted by a permutation automaton, then its minimal DFA is also a permutation group, but this group is transitive (since every state is accessible from the initial state). Thus your subclass is actually ...

1

This is a good example of how bad notation can make simple questions much more difficult. (1) There is no reason to introduce grammars. You may as well denote by $L_1$ the language accepted by $M_1$ and by $L_2$ the language accepted by $M_2$. (2) Let us denote by $L^c$ the complement of a language $L$. Then your first (correct) equality amounts to prove ...

0

In general the intersection of two CFLs is not context free. Can you come up with an example? Mouse over the grey area below for an example. (It is a theorem that the intersection of a context free language with a regular language is context free.) So the description of a PDA recognizing $P_1 \cap P_2$ does not necessarily exist.

0

The machine $A$ does quite a job of deciding its own language, so to speak. The only part where $A$ fails to decide its language is when the input has length $n$ wherer $n$ is a prime number. Thus, to decide the language of $A$, one only has to: check if the input size is a prime number. If this is the case, reject the input. if the input size if a ...

0

Every finite language is regular. Pick any language of which you know it isn't regular and write it as the union of infinitely many finite languages.

0

Hint: There are only finitely many states to the Rubik's cube (43,252,003,274,489,856,000, or about 43 quintillion, according to the Wikipedia page.) Base your finite state machine on those states.

2

Since $P \subseteq NP$, $NP^P = NP$. Nondeterministic programs are an extension of deterministic programs. They are just programs with a jump-and-branch command added. So every deterministic program is also a nondeterminnistic program that doesn't use jump-and-branch, so adding the oracle gives no additional computability.

0

Follow the steps in the following order 1)Remove ε production S→ASA|AS|SA|A( You can ignore S->S ) A→aa 2)Remove Unit Production(Non Terminal->Single Non Terminal) Here we have unit production S->A S→ASA|AS|SA|aa A->aa 3)Remove Long Production(restructure the grammar such that R.H.S. have either 2 Non Terminal or single Terminal symbol) ...

Top 50 recent answers are included