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

### How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state

I’m trying to design a DFA which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table ...
34 views

### k-limited solution for PCP

So there's following problem, that has been bugging me for the last few days: A solution of a PCP $i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
32 views

28 views

70 views

### Finding the upper bound of states in Minimal Deterministic Finite Automata

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $L(A_1) \backslash L(A_2)$, where $A_1$ is a Deterministic Finite ...
52 views

### Does the order of ripping off the states matter?

Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
25 views

120 views

### Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
39 views

### How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
77 views

### Multiple paths for a accepting string in NFA?

If a string(w) is accepted by an NFA, then corresponding to w, can there be multiple paths each starting from the start state and ending at an accepting state?
34 views

### Automaton-based model checking on finite traces

I want to check whether a formula in finite LTL is valid on a finite, linear trace. For infite traces I would create a Kripke structure of the trace and a Büchi automaton for the negated formula, ...
36 views

### Construct regular expression that contains the substring

I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring. So far, the even number of b's can be ...
26 views

### If T is a Turing Machine, what are the languages Accept(T), Reject(T) and Loop(T)?

I have the following Turing machine: I am asked what are the langauges accept(T), reject(T) and loop(T). This seems to me a trivial question as from the looks of it, accept(T) is the language of all ...
46 views

### Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1

I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA ...
37 views

### convert RE to NFA

The Regular Expression i am having trouble with is the following a(b|bcc*)*c. My main concern is what do i do with the c*? I can lay the rest of the diagram correctly (i think) but that part is ...
33 views

### Minimisatiom using Myhill-Nerode Theorem

I have recently studied the Myhill–Nerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because ...