# Tagged Questions

Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.

42 views

### DFAs can be encoded as input/output for a neural network?

I would encode DFAs (Deterministic Finite State automata) as output (or input) of a neural network for a supervised learning; it is well-known [1] that efficacy of neural network training strongly ...
16 views

### DFA minimization using Myhill-Nerode Theorem

I must've got a blockade or something, I just can't figure out step 2 here: http://www.tutorialspoint.com/automata_theory/dfa_minimization.htm I get all the other steps, I get the initial setup of ...
27 views

### Does a NFA/DFA need a failure state?

I'm learning for my exam in theoretical computer science and I'm not sure about it, because I got different sources with different answers. So I wanted to ask here: If I draw a NFA/DFA and I maybe ...
16 views

### Prove that half(L) is also regular if L is a regular language [duplicate]

Given a regular language $L \subseteq \sum^*$ prove that the language $half(L) = \{w \space | \space ww \space \in \space L \}$ is also a regular language. -- Please give a hint or two. Have ...
40 views

78 views

### Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
56 views

### What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ...
463 views

### Is it possible to build DFA for odd-length words with 1 in the middle?

$L := \{w \in \{0,1\}^* |$the length of $w$ is odd $\wedge$ 1 is in the middle of $w\}$ So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and ...
57 views

I was given the following question. Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it accepts or not): ...
70 views

### Where Can I Find DFA Practice?

Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so ...
72 views

### If L is a regular language, how to prove that L' is also regular?

I've been trying to construct a proof of the following statement the whole day but I got stuck: If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the ...
30 views

### Is the language of all DFAs that accept the empty language regular?

Is $E_{DFA}$ in the class of regular languages? $\qquad E_{DFA} = \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$ My argument is that it is because all of the DFAs in $E_{DFA}$ ...
16 views

### What is the effect of having a transition in an epsilon-NFA upon “$\epsilon$,0”?

When a transition between two states is achieved via any of the symbols $\epsilon,0$, how does the $\epsilon$ effect the transition between the two states? Does it simply mean that the $0$ is ignored,...
27 views

### similar language by two DFA then why wrong answer

I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer ...
30 views

### Design the grammar for the following [closed]

Design the grammar for the following: L = (a^n)w(w^r)(b^n) where n>=0 and w={a,b}
46 views

### What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...
111 views

### How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. "Similarity"...
59 views

### What is the difference between finite automata and Büchi automata?

as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented. From an assignment I'm working on, this automaton can be depicted ...
51 views

### construct a dfa that accepts odd consecutive number of 0's and 1's

this dfa should accept only consecutive odd number of both 0's and 1's. example: 10001,1110001,10,01,011101. How can I draw its diagram?
31 views

### Isomorphism of a DFA and the minimal DFA

I have a DFA A, I minimize A and the minimized DFA obtained is M. My question is if in general A and M are isomorphic?
95 views

### Design an NFA to accept a, ad, abc, abd, but not e, abcd?

I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that? Updated I modified the diagram in another attempt:
I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...