Tag: finite

Is it possible to construct a finite state automata for a decimal adder?

Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $ \Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is accepted, but 2#97#104 is not. Is it possible to find a finite automata for such a language ? I am aware of binary addition but I cannot fathom how decimal addition could be carried out using a DFA .

Maximization problem on finite collection of finite sets


Problem

I am considering the following maximization problem:

  • Input is a finite collection of finite sets $ \mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$ .
  • Goal is to find a subset $ G \subseteq \mathcal{F}$ that maximizes $ |G| \times |\bigcap G|$ where
    • $ |G|$ is the cardinality of the set $ G$ , and
    • $ \bigcap G = \bigcap \{X_{i_1}, X_{i_2}, \ldots, X_{i_m} \}$ .

As an example, for the collection $ $ \mathcal{F} = \{ \{a, b, c\}, \{a, b, c, x\}, \{b, c, y\}, \{a, b, c, z\} \}, $ $ the maximizing subset is $ G = \{ \{a, b, c\}, \{a, b, c, x\}, \{a, b, c, z\} \}$ and the score is $ 3 \times |\{a, b, c\}| = 9$ .

Note: the score of $ \mathcal{F}$ itself is $ 4 \times |\{b, c\}| = 8$ .

Question

I am planning to use a procedure of this problem for compressing data (represented by finite collections of finite sets). However, I don’t have any good idea to solve this problem efficiently. As yow know, we can solve this by enumerating all the collections of $ \mathcal{F}$ ; but, it’s too slow for practical use.

Is there a polynomial-time or some kind of efficient algorithm for this problem? Or, does this problem belong to the complexity class that cannot be solved in polynomial time?

Is the languague L={, M accepts a finite amount of words} decdidable?

Is $ L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM.

I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem.

This my try : Let f(<m,w>) be a function which works in the following way :

  1. Run w on M
  2. If M accepts Construct a TM Mwhich accepts only the word w and return M
  3. If M rejects Construct a TM Mwhich accepts everything. Return M

So if m is in $ A_{TM}= \{<M,w>|M \ accepts \ w\}$ we know that f(<m,w>) is in L. If m is not in A then we know that f(<m,w>) does accept every word and therefore infinity words. So f(<m,w>) not in L.

Is this a correct mapping reduction ?

Deterministic Finite Automata vs Java

You need to select a device controller. You have two options: Option 1: Implement with a DFA Option 2: Implement using Java The primary advantage of a DFA over a program written in Java is as follows:

Answer choices:

  • A DFA requires fewer computational resources
  • A DFA is faster than a program in Java
  • Running a DFA costs less than running a program written in Java
  • It doesn’t matter if we use a DFA or a program written in Java, as long as it gets the job done

When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?

A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current character being read.

If the machine halts when it’s in an accepted state and at the same time the whole input has been consumed the input string is considered to be accepted.

Now, when introduce $ \epsilon$ transitions the machine doesn’t necessarily halt when the whole input string has been consumed, for it is possible that there are still $ \epsilon$ transitions available.

Suppose we have a NFA that is in an accepted state and also that the whole input has been consumed, but there are still $ \epsilon$ transitions available in this state, can we considered the input string to be accepted or do we need to "follow the trail" of $ \epsilon$ transitions until we reach a state where no other transition is available?