# 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,193 questions
Filter by
Sorted by
Tagged with
18 views

### Can nfa consume more than one letter at a time

If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time. like the example shown
24 views

### NFA/DFA for $L= \{a^n b^n a | n\ge0\}$

I have made two DFA’s for $L= \{a^n b^n a | n\ge0\}$. First one has several states. The second one is accepting an empty string also. Somebody please guide me the correct one. Zulfi.
12 views

### Regular expression containing lambda

What is the meaning of lambda here: $$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$. I know that lambda is used in the context of NFA? Let's suppose we break down the expression ...
22 views

### Intersection of two DFA's

I am trying to understand the intersection of 2 DFA's. I got the following link: Intersection of 2 DFAs I can't understand why they have not used the symbol 'b'. In the DFA's they have symbol 'b' also ...
21 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 ...
44 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 ...
21 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 ...
40 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,...
14 views

### construct transition table from equivalence of dfa-minimization

I'm trying to minimize a DFA. From the state transition diagram, I have formed the table: And the 0-equivalence is : {q0,q1,q3,q4,q5,q6,q7},{q2} And 2-equivalence is {q0,q4},{q6},{q1,q7},{q3,q5},{...
27 views

### Why does this finite state machine state transition diagram solution has more states than my solution?

I can't figure out what is wrong with my solution and why does it differ from book's solution. I think the only thing that matters is the previous state of A so that there should be two states, one ...
20 views

### Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters

I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
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 ...