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
2 votes
1 answer
69 views

Regex where all strings containing an even number of 0's:

Question is to construct a regex where all strings containing an even number of 0's: By constructing DFA graphically, it is $$(1^*+01^*0)^* $$ But it is also $$1^*(01^*01^*)^*$$ Can we prove that they ...
0 votes
0 answers
9 views

RE to NFA conversion JFLAP [closed]

Having this regular expression ((0 + 1)(11)* + 0)* I get this NFA according to me: I'm trying to compare it with the RE on JFlap and it says it's not equivalent ...
1 vote
2 answers
57 views

Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
3 votes
3 answers
1k views

DFA that accepts strings whose 10th symbol from the right end is 1

Problem is "Constructing a DFA accepting set of all strings whose 10th symbol from the right end is $1$ over $\{0,1\}$" The NFA is easy $$(0+1)^*1(0+1)^9$$ but DFA has to have minimum $2^{10}...
1 vote
2 answers
52 views

Finite state machine that accepts every word with at least one c, or different value of parity of the counts of a's and c's

few weeks ago I had an exam in automata theory course and I've been asked to write the following non-deterministic finite automata Write a NFA which accepts the following language - the language ...
  • 11
3 votes
1 answer
612 views

Can we transfer every DFA to DFAs with start state having no in edge?

The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
1 vote
1 answer
61 views

Transform a non-regular language into a regular one using sort

Is there a way where sort turns a non regular language into a regular one. What I mean by sort is this: Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively. ...
-1 votes
0 answers
43 views

Intermediate DFA question- divisibility

The question is "The set of strings such that the number of 0's is divisible by five, and the number of 1 's is divisible by 3 over the alphabet {0,1}" All I could do is just 0's that are ...
0 votes
1 answer
46 views

Is there a typo in this excerpt from the book?

Michael Sipser's Introduction to Theory of Computation: Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a ...
  • 3
1 vote
1 answer
66 views

Constructing a deterministic finite automaton from a particular regular expression

This is the given question- Construct a DFA over the alphabet {0,1} such that it accepts all strings containing even number of 0's OR the number of 1's divisible by 3. The very first problem I've ...
2 votes
0 answers
145 views

What extension of a finite-state machine is modeled by aliasing inputs?

Recently, I’ve been interested in the console of the Source game engine, more specifically, its alias command, which allows one command to invoke others. It may ...
-4 votes
1 answer
38 views

Describe the language accepted by the DFA

Describe the language accepted by the DFA shown above
0 votes
1 answer
49 views

Is pumping lemma not applicable for every 'long enough' string in the language?

I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
  • 15
1 vote
1 answer
60 views

What are non-isomorphic NFAs

I came across the following problem while doing my Formal Language class assignment and hope someone can give me some hints: I have $\Sigma = \{0,1\}$ and $L=\{x0a \mid x \in \Sigma^*, a \in \Sigma\}$...
  • 15
0 votes
1 answer
43 views

Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
0 votes
2 answers
63 views

Can a DFA have multiple of the same state?

I need to create a DFA for a sequential order of states e.g. A -> B -> C -> B -> A and so on, where 'A' is the start and finish state, 1 is a transition to the next state and 0 just loops ...
0 votes
1 answer
63 views

Explain meaning of states and transitions for DFA that accepts two binary words (a,b) with b = 5a

I was provided with the solution to the language being represented. An example of accepted input would be [001][101]. The DFA that would recognize this language is below. What do the states represent?...
  • 11
1 vote
1 answer
95 views

Getting an NFA with only one initial and final state without epsilon transitions

Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions,...
  • 115
0 votes
1 answer
29 views

Designing DFA for a language

I am working on designing a DFA with the language $a^i b^j c^k$ such that $i + j + k$ is odd I thought along the following lines: $i+j+k$ is odd $\Rightarrow$ two of them are even and one is odd or ...
  • 131
1 vote
1 answer
89 views

How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?

Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row. Let $\Sigma_2 = \left\{ \begin{bmatrix}0\\ 0\end{bmatrix}, \begin{bmatrix}0\\ 1\end{...
  • 11
0 votes
0 answers
33 views

prove that Every DPDA has an equivalent DPDA that always reads the entire input string

I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
  • 1
1 vote
1 answer
101 views

What is the smallest NFA you can design for {a^n : n =/= 1003}

What is the smallest NFA that could be design for a^n where n!=1003? I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
  • 13
0 votes
0 answers
32 views

Is there any way to tell which states are final states in a finite state automata given only its grammar?

Problem In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
-4 votes
2 answers
73 views

A string that contains aabb, does this work?

Can you verify this like please bro please tell me the answer to my question
3 votes
1 answer
62 views

Building the minimal automaton from the syntactic monoid of a language

I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
  • 448
0 votes
0 answers
23 views

Meaning of term $L(\bar{n})$

I was studying a few terms on finite automatas, and came across the following terms: $L(\bar{n})$ and $\overline{L(n)}$ The latter term stands for complement of a given NFA, but what does $L(\bar{n})$ ...
  • 115
0 votes
2 answers
57 views

Every DFA accepting a finite language must contain a dead state?

I came a across a question where there were some statements made on Finite Automata, DFA and their states. One such statements in the question was that a "Every DFA accepting a finite language ...
  • 115
0 votes
0 answers
35 views

How does the regular expression '^(a+)+$' lead to this specific NFA?

OWAPS has an article on ReDoS (archived). In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities. They provide this illustration of ...
-1 votes
1 answer
25 views

find the minimization of the dfa

so this is the question , I have to minimize this DFA this is How I did it but when I checked for answers , this is what it was, can someone please explain to me what mistake I made? I have been ...
0 votes
0 answers
23 views

In Pumpin Lemma, let's say we have a decomposition of the string s = xyz, is it necessary for x to take the automaton through distinct states?

I understand what Pumping Lemma is, how it works and also understand it's proof. The gist is that it uses "Pigeon Hole" principle to guarentee us a repeatation in the sequence of states and ...
0 votes
1 answer
40 views

Does every regular expression describe only 1 language?

If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it Also, $...
-1 votes
3 answers
49 views

Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular

I understand that pumping lemma can only be used to prove that a certain language is "non-regular", it cannot be used for proving regularity But since, it's a property of regular language, ...
0 votes
1 answer
52 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
3 votes
1 answer
470 views

When converting a epsilon NFA to NFA to DFA, how to handle the start state?

Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3 We know when converting from epsilon NFA to NFA, we apply the following formula for ...
0 votes
1 answer
171 views

Conversion of epsilon NFA to DFA, handling epsilon transitions

I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs" Case 0: Michael Sipser asks us to handle ...
0 votes
2 answers
119 views

Automata: Are there algorithms to judge whether two automata are isomorphic?

When I want to judge whether two regular forms represent the same language, I have learned the next method: create the (non-deterministic) finite-state automata which accepts the language the given ...
  • 1
1 vote
1 answer
74 views

Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states

Let's say we have a NFA as follows: It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon My question is do we take epsilon transition ...
1 vote
1 answer
76 views

Is the equivalence problem of a CFG and a FSM decidable?

I have the following problem: Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
0 votes
1 answer
106 views

Confusion regarding the intuition behind epsilon transition in NFA

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 ) Let's use this E-NFA as an example My question is, do we ...
0 votes
1 answer
73 views

When converting from nfa to dfa, do we always ignore the trap state?

Let's say we have a NFA such as follows: We know it's equivalent DFA is follows, after minimization: We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of ...
0 votes
1 answer
14 views

Equivalence of echo state networks and DFAs/NFAs

Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
  • 11
1 vote
1 answer
49 views

Is $L = \{a^{p^2}\mid p\text{ is a prime}\}$ regular?

By pumping lemma, we choose the word $w=a^{p^2}$ that the decomposing is $[a^sa^ta^{p-s-t}]^p$ such that $u=a^s,v^i=a^t,x=a^{p-s-t}$ $[a^sa^{it}a^{p-s-t}]^p=[a^{p+it-t}]^p$ We choose i=p+1,we get $ [a^...
0 votes
1 answer
44 views

Why Regular Grammar is Left/Right Linear?

From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules) But, my question is why it is mandatory? Can't we ...
1 vote
1 answer
39 views

Check whether a regular expression is correct

I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct? ...
  • 150k
0 votes
1 answer
33 views

What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?

I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
0 votes
2 answers
105 views

If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?

L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1. Is L1 regular under the property that regular languages are closed ...
0 votes
0 answers
22 views

How are we sure choose is going to halt? question regarding a section from Elaine Rich's Automata, Computability and Complexity book?

I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used. choose (x ...
  • 11
4 votes
0 answers
70 views

Inverse operation to concatenation for regular languages

I'm currently in need of the inverse operation of the concatenation of 2 regular languages. Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
0 votes
1 answer
44 views

Why must 2 distinct strings go to the same state in a DFA?

I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA. Is it that if there are n words and m states, where there are more ...
0 votes
0 answers
17 views

complement of {a^lb^mc^n:n>l+m}

If we have this language $ L = \{a^mb^nc^n:m,n \in N\}$, would its complement be $\{a,b,c\}^* \setminus L = L^\complement = \{c^nb^na^m:m,n \in N\}$? This was the professor's answer, which I find ...

1
2 3 4 5
34