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,534 questions
Filter by
Sorted by
Tagged with
814 views

Automaton for telling whether a binary number is a multiple of 3

I am designing an automata which determines whether a binary number is divisible by 3: $$\{x \in \{0, 1\}^* \mid \text{x represents a multiple of three in binary} \}$$ 0 1 0F 0 1 1 2 0 2 1 2 ...
7 views

Compare powers of PDM and FSM with Turing machine

Compare powers of PDM and FSM with Turing machine.
98 views

A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

I am confused by the following claim: Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
17 views

1k views

Proof that for 2n nodes of +1 and -1 position doesn't count

I'm having a hard time understanding how to solve this problem for my Computer Science 101 class. On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a ...
61 views

Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
22 views

I was trying to minimize given DFA: a b -> 1 4 2 F 2 1 1 3 1 4 F 4 1 1 I've watched few videos about solving this problem and decided to use the equivalance method. While doing it I've come ...
30 views

How do we decide whether or not to accept $\epsilon$ in dfa?

Can I exclude $\epsilon$? Will that make a difference. This is really confusing me. It seems everything could contain $\epsilon$. Is there some way of thinking to realize this contains $\epsilon$ or ...
21 views

How to build a minimal string matching DFA with limited memory?

I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
32 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
56 views

How do I create a finite state automata for addition in ternary system?

I've been scratching my head with this one for a few hours now, but am feeling to stupid to comprehend how it is to be done. I can't understand the way even the state table should be built for this ...
51 views

epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?

Source of this question and problem: https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa This is the question: So in this figure there are my 1 confusion-: Don't we need a empty ...
51 views

When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?

The question is-: THIS is the transition table for NFA-: Final result as shown in youtube video. https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49 ...
36 views

What does DFA that accepts at least 1 a or at least 1 b mean?

What are the language accepted by this DFA? The truth table of OR-: But I am unable to deduct what this dfa will accept? Say-: P=at least 1 a Q=at least 1 b So DFA should accept both ab. Or in ...
33 views

Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
38 views

NFA has power to be in several states at once implies NFA has ability to guess about its input. How?

I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
34 views

DFA for {w|w contains a substring of length at most 5 that has at least three 1's}

I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, ...
31 views

conversion of epsilon NFA to NFA

I was given below task: Eliminate Epsilon-transitions in below automata My solution: Is it correct that stage 1 is actually one of the final stages? How does it work in given example? We have ...
34 views

conversion of NFA to DFA (omitted states)

I've been given following task: Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction) My solution to this: Would like to ask for a ...
14 views

Problems with simulating NFA with DFA

I have this NFA: I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
46 views

165 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
I came up with this proof for the following theorem: If $L$ is a language produced by an nfa, then there exists a dfa $M$ where $L(M) = L$. Is it correct? If it's not, what are the flaws of my proof,...