# Questions tagged [finite-automata]

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.

1,374 questions
Filter by
Sorted by
Tagged with
30 views

### What exactly is “pattern matching”?

I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions. But is there a precise definition? In particular, it seems that it has to do with ...
84 views

### Meaning of $a\lor b \to b' \lor c'$

So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...
28 views

### Use ML to create a graph

I'm currently looking for literature/papers on machine learning techniques to create structures. In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I ...
559 views

### Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
236 views

### No nonfinal states in NFA

I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$. What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can ...
118 views

73 views

### Prove that a language is bounded if and only if it's finite

Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
79 views

### Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
43 views

### Example of a locally trivial semigroup

I was having a look at the block product principle for finite monoids. I wanted to see the derivation of LTT = Acom$*$LI, using an example. But I can't come up with a non-trivial example of a monoid ...
28 views

### Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
### Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?
I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm: But I couldn't understand what does $E(n)$ and \$E(...