Tagged Questions

The tag has no usage guidance.

564 views

Can you hide a letter without losing information?

Consider the following game between Alice and Bob. $\Sigma$ is a finite nonempty alphabet, $\Delta \notin \Sigma$ denotes a special symbol, and $k > 0$ is a positive integer constant representing ...
459 views

Finite variation and idempotent languages and automata.

Let $L$ be a regular language over alphabet $\Sigma$ and let $A:=(Q,\Sigma,\delta, q_0, F)$ be the minimal DFA recognizing $L$. For every $w\in \Sigma^*$ define the variation of $w$ w.r.t. $L$ by \...
879 views

Transition Graph per alphabet? [closed]

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
382 views

Growth zeta-functions of regular languages

Dear All, my following question may be known and ought to be known, so in case it is folklore please could you give me the references. To start, it is obvious that growth of rational languages are ...
328 views

Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
634 views