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.

Filter by
Sorted by
Tagged with
1
vote
1answer
15 views

What is the correct way to draw NFA of RE (a|b|c)?

We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this But my professor told me it is wrong, the correct way is So, I checked it ...
0
votes
0answers
8 views

Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}

I'm having a hard time trying to write a two tape Turing machine I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...
-3
votes
1answer
46 views

Design an NFA to recognize the given language. (Table and diagram) [closed]

Construct an NFA over {a, b} that accept strings having aa as substring. Construct an NFA over {0,1,} that contain 0110 or 1001. Construct an NFA over {a, b} that accept strings starting with a ending ...
0
votes
1answer
19 views

What does c represent in Sipser's explanation of the modified post correspondence problem Introduction to the Theory of Computation book?

I'm supposed to perform actions corresponding to the different steps in Sipser's explanation of the Modified Post Correspondence Problem, but I'm not sure I understand the third step. The part I'm ...
0
votes
1answer
12 views

What is the meaning of Sub_tm in this context?

Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place. Prove that the following is undecidable: $SUB_{TM} = \...
-2
votes
0answers
39 views

Prove that {⟨M,u⟩ : M is a DFA and there exists w ∈ L(M) such that u is a subword of w} is decidable

Let $u,w\in\Sigma^*$. We say $u$ is a subword of $w$ if there exist words $x,y\in\Sigma^*$ such that $w = xuy$. Define the language $$\mathrm{SUB}_{\mathrm{DFA}} = \{\langle M,u\rangle : M\text{ is a ...
6
votes
2answers
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 ...
-1
votes
0answers
22 views

What is Overlapping in Finite Automata

What is meant by "overlapping" in Finite Automatas?
1
vote
0answers
50 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 ...
0
votes
1answer
18 views

DFA minimazation (dead state)

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 ...
0
votes
1answer
24 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 ...
-2
votes
0answers
25 views

What languages does a dfa that accepts question1) ab or ba question2) ab and ba contain?

I am trying to figure out what languages should be accepted by dfa that accepts ab or ba. ab and ba. I am confused how we determine this? Do we use Truth table? If yes how? I know truth table for ...
2
votes
0answers
19 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 ...
2
votes
1answer
30 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 ...
0
votes
0answers
18 views

Structural induction proofs for regular expression [closed]

Let $RE$ be the set of regular expressions over the alphabet {a,b} How do I go about proving the following using structural induction For each r $\in$ $RE$ there is a $r'$ in $RE$ such that $\epsilon$ ...
0
votes
1answer
55 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 ...
1
vote
1answer
29 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 ...
0
votes
2answers
41 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 ...
-1
votes
0answers
21 views

NFA-$\epsilon$ for $a.(a+b)^*.b.b$

The difference between these is $\epsilon$ during concatenation. I think the second one is correct. But I am confused because first one is shown in my textbook. I think both mean same but I am not ...
-2
votes
0answers
52 views

Regular grammar for language that does not contain "abab"

I tried this : $V = \{S,A,B\}$ and $T = \{a,b\}$. $S \rightarrow aS | \epsilon | abaAS | BS$ $A \rightarrow a | aA$ $B \rightarrow bB | \epsilon$ Any thoughts/objections?
-2
votes
1answer
29 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 ...
1
vote
1answer
29 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 ...
1
vote
2answers
31 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 "...
0
votes
1answer
25 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, ...
0
votes
0answers
27 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 ...
1
vote
1answer
31 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 ...
0
votes
1answer
13 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 ...
0
votes
1answer
43 views

Need help with constructing a DFA

I am trying to construct the DFA that accepts the following language $$ L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...
1
vote
1answer
25 views

What is the difference between these 2 dfas for binary strings ending with 00?

The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation. Now I know what that second figure means, it means it also accepts ...
2
votes
1answer
39 views

Are Nondeterministic Finite Automata not allowed 'sink-states'?

By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
2
votes
1answer
117 views

How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?

Context-: A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ. https://www.univ-orleans.fr/lifo/...
3
votes
4answers
164 views

Are there any programming languages that support state machines in their standard library?

State machines are a fundamental computer science concept and in many senarios they are the simplest way to implement a process or program. However, most programming languages don't support them ...
-1
votes
1answer
48 views

Design a DFA that accepts numbers whose sum of digits is $2 \mod 3$

Design a DFA that accepts language $$L = \left\{ x \in \{ 0, 1, 2 \} : \text{ sum of digits in } x \text{ is } 2 \mod 3 \right\}$$ How to make a DFA for this? I have no idea how to solve this dfa ...
-3
votes
1answer
48 views

Design a DFA that accepts language L={ x in (0,1)* | the third bit from x from its right end is 1}

this is very confusing question. I am having no idea to solve it, can you please guide me here?
0
votes
1answer
46 views

DFA for even number of 1's

My attempt at solution-: Solution by a teacher-: Both are giving same answer, is the one that I made correct?
-2
votes
2answers
61 views

Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
0
votes
1answer
36 views

Prove the class of regular languages is closed or not closed under the operations below

Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
0
votes
1answer
41 views

Size of minimal DFA

Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
1
vote
2answers
37 views

What is the minimum pumping lemma length of $01^*0^*1$?

I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$: Set a PL. I chose $p=2$ Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
0
votes
0answers
47 views

If $L$ is regular, is $L/w = \{x\mid wx\in L\}$ regular?

I'm trying to see if the language $L/w = \{x\mid wx\in L\}$ is regular given that $L$ itself is regular. It seems to me that if $L=L(A)$ for the NFA $A = (Q, \Sigma, \delta, S, F)$, then the NFA $A'$ ...
2
votes
2answers
57 views

If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that $$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$ I thought I could take a DFA which computes ...
0
votes
2answers
135 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 ...
0
votes
0answers
12 views

Need literature on First order logic definibility through Automata

Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
0
votes
0answers
67 views

My proof for equivalence of DFA and NFA

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,...
0
votes
1answer
47 views

How to convert this regular grammar into a finite state automaton?

In a French course (p. 13) there is a language of words of {a,b,c} containing at least one occurrence of the string bac. The ...
1
vote
1answer
23 views

Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?

I have a question that says that the complement of a regular language given as: $L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
1
vote
1answer
30 views

Designing a NFA that accept the set of strings that contain an even number of substrings 01

I'm new in theory of computation. Here {0,1} set of input symbols. I tried to make the NFA from L(M)= set of all accepted strings, but unable to complete it. Can someone give some hints that how ...
0
votes
0answers
35 views

Prove that the language such that the concatenation of any string with its complement is accepted by a regular language is regular [duplicate]

I’m trying to solve the following question: Suppose you have a regular language L with the alphabet {0,1}*. Show the language L’ = {x : x x_c \in L} is also regular. x_c is the flipped version of x ...
4
votes
2answers
74 views

Is the language "substrings of a regular language that are over half the length of the superstring" regular?

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular? I was provided the ...
0
votes
0answers
25 views

DFA and RE find out the language. Please can you explain?

Find the regular expression describing following languages over alphabet {0, 1}*. ...

1
2 3 4 5
31