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
0
votes
1answer
60 views

Copy operation in under 9 states?

There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
3
votes
3answers
70 views

Minimal DFA for $1\Sigma^*0$

What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?
1
vote
2answers
451 views

Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
2
votes
2answers
233 views

Use DFA minimization on LR(1) states

I have recently started reading more about context-free parsing techniques, in particular LR parsing. As I have read, LR state transition graph (or table(s)) used for finding handles in sentential ...
6
votes
1answer
48 views

Determine the number of reachable states in a subset construction?

Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?
1
vote
2answers
58 views

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular. If we assume on the contrary, then there ...
2
votes
1answer
54 views

Conversion of $\epsilon$-NFA to a DFA

So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her ...
0
votes
3answers
276 views

Is the set of strings with equal number of 010’s and 101’s regular?

Consider the language $$L = \{ w\in \{ 0, 1\}^*: \#_{010}(w) = \#_{101}(w) \}$$ Is $L$ is regular? If it is not regular, can we prove that using the pumping lemma (only with pumping down)?
1
vote
1answer
37 views

Regular Languages and Separating Suffixes

Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it. Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \...
0
votes
1answer
95 views

building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

$\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$ I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ ...
0
votes
2answers
154 views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
0
votes
1answer
57 views

Conversion of RE to NFA

I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct? And in what situation we add ...
3
votes
1answer
195 views

Complete explanation of state elimination methods [duplicate]

I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method". In other words, what is the general idea, and what is the ...
2
votes
1answer
155 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
4
votes
1answer
43 views

Is there a method to generate the complement of a context-free grammar?

Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
4
votes
2answers
808 views

Why is this automaton considered DFA?

So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string ...
0
votes
2answers
64 views

Determine if the language of words with same number of 1's and 2's is context-free or not

$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$ I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
0
votes
1answer
75 views

What does 'Describe the language of this automaton' mean?

I've been asked to do this as part of an assignment. Here is the automaton: I understood it as describing in terms of the 5 tuples so I wrote: The states are as follows: Q = {A, B, C} The alphabet ...
2
votes
2answers
37 views

Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
0
votes
1answer
31 views

Create an Finite Deterministic Automata for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
2
votes
1answer
78 views

Language Containment of Automata

If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?
0
votes
0answers
54 views

Possibly empty string in a DFA

I am trying to construct a DFA with this language L - all strings consisting of 0’s followed by a (possibly empty) string of 1’s followed by a (possibly empty) string of 0’s. I made the start state ...
0
votes
1answer
40 views

Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
1
vote
1answer
84 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 ...
0
votes
1answer
560 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,...
1
vote
3answers
172 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 ...
2
votes
1answer
54 views

Minimal DFA accepting strings whose length is divisible by $x$ or $y$

Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$. After trying various values of $x$ and $y$, I noticed made the following observation: If one ...
2
votes
0answers
22 views

closure property violated by palindrome language

It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
18
votes
1answer
535 views

Exponential separation between NFAs and DFAs in the presence of unions

For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an ...
2
votes
1answer
32 views

Why can PDAs have infinite stack but FSMs cannot have infinite state?

A Finite State Machine cannot accept the language $$L = \{ 0^n1^n \mid n > 0 \} $$ because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can ...
1
vote
1answer
87 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
1
vote
1answer
57 views

Closure of regular languages under “inverse second half”

Theorem. Show that if $L$ is regular, then so is $$ \varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
0
votes
1answer
50 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
4
votes
1answer
124 views

Kleene's Theorem and TMs

I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language? Is this ...
1
vote
1answer
44 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
0
votes
1answer
137 views

How to construct an NFA Ai for the given Regular property P1 and P2?

Let AP = {a; b; c}. Consider the following regular safety properties: (a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds. (b) P2: Between two neighbouring occurrences ...
0
votes
0answers
21 views

PDA Explanation

{a^2i.b^3i | i ≥ 0 } How would I draw this? I just started learning about pda's and I'm not sure where to start. I've looked at youtube videos explaining pda's but I'm still not understanding how to ...
0
votes
1answer
39 views

Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

This problem is from an exercise sheet so it would be nice if you could guide me to the solution. The problem: For $ k \in \mathbb{N}\setminus\{0\}$ let $$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
0
votes
0answers
24 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
0
votes
1answer
67 views

Turing machine state transition diagram vs finite state machine state transition diagram

If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would ...
0
votes
1answer
39 views

Convert the given NFA to DFA

I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$. First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get $L\...
1
vote
2answers
40 views

DFA to accept a String containing even number of both A and B, but rejects empty String

I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε) I have already drawn the DFA which accepts the above language, without rejecting the ...
0
votes
1answer
26 views

How do i prove this language is regular? [duplicate]

I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
1
vote
1answer
552 views

What does it mean for a grammar to be LR(0)?

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0). For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
0
votes
2answers
86 views

Kleene star operations

Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{∗}$ and $𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages. a. If $𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $L_1$. b.Let $\Lambda \...
1
vote
2answers
677 views

How to convert this DFA with multiple final states to a regular expression? (State elimination method)

So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4. I want to ...
0
votes
1answer
40 views

Converting Moore to Mealy When first Node has Output

This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a ...
0
votes
1answer
34 views

Read regular Expression from NFA

Good evening everyone! Can someone help me with the following task? So we have this NFA: I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
5
votes
2answers
5k views

Why is every finite language A ⊆ Σ* regular

So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can ...
1
vote
1answer
21 views

Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG). I suspect that languages like $\text{L} = \{...

1
2 3 4 5
28