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.
0
votes
0answers
21 views
Finite State Automata for English regular main verbs
I would like to build an FSA to recognise english regular main verbs. E.g. walk, play, call, look, etc... with following morphological forms: (1) base form, (2) third person singular (-s), (3) present ...
0
votes
0answers
33 views
Can the pseudo-random-sequence generator be described as a finite state automaton?
I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot ...
1
vote
1answer
27 views
Intersection of two incomplete DFAs
Let assume that I have the following two automata A1 and A2 :
I have to do the intersection of the two, so I did this :
My question is related to the "∅". If I have two incomplete automata without ...
0
votes
0answers
14 views
What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]
Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.?
I would like to know some ...
-1
votes
0answers
12 views
How do we obtain a dfa to accept strings of a’s and b’s such that l = {w| w ∈ (a + b)* } such that na(w) mod 3 = 0 and nb(w) mod 2 = 0?
It's an assignment question but I do not completely understand how to do it. I have basic knowledge in the subject, I just need some help as soon as possible.
2
votes
2answers
374 views
Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
3
votes
2answers
56 views
The complexity of the reachability-coreachability analysis of a finite state machine
Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is ...
1
vote
0answers
26 views
RO turing machine with finite memory
Consider the following:
A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length.
I need to determine whether if the ...
-3
votes
2answers
28 views
DFA accept 00 as a substring
How can design this question if we have an equation like that
={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...
0
votes
1answer
39 views
What do I need to show that music theory is a reugular language not a singularity? [closed]
After writing a lot of tablature, it is obvious to me music is a regular language but I can't find anything in the literature so I am trying to understand what other people consider sufficient proof ...
1
vote
1answer
30 views
finding separating words (Nerode)
i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
5
votes
2answers
219 views
Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.
I saw the answers to this question: are regular languages closed under division
and the proof sketch is not ...
1
vote
1answer
27 views
Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?
Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and ...
0
votes
2answers
25 views
Does this DFA describe this regular expression?
For the expression (ab)*ba I came up with the following (very poorly drawn):
However, this was not the correct answer - apparently the solution requires five ...
2
votes
2answers
53 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
0
votes
1answer
18 views
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?
Just for Understanding (don't solve the below one),
eg:
\begin{align}
S &\rightarrow B/A, \\
1B &\...
2
votes
1answer
51 views
How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount
I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is
$$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
0
votes
1answer
16 views
Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}
I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help
Thanks in Advance!
1
vote
1answer
29 views
If a DFA were implemented as a circuit, what would the empty string correspond to as input?
Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$.
Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up ...
1
vote
0answers
20 views
Decision problems involving finite automata
A finite automaton (FA), A, may accept or reject its own encoding, {A}. A machine, M, can be written that accepts {A} iff A rejects {A}. Turing gave a famous proof that M is not an FA. The proof ...
3
votes
3answers
206 views
Can product DFA for intersection of two disjoint languages be minimal?
I know that it isn't necessary that cross product automaton for two minimal DFAs be minimal, but according to my analysis, if two DFAs do not have any common string then their cross product of minimal ...
1
vote
1answer
209 views
Define a DFA that accepts all even length binary strings that don't contain the substring “111”?
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly ...
0
votes
0answers
21 views
Extended regular expression and intersection of languages of DFAs
I'm new with extended regular expression and I want to know if there are connections with the intersection non-emptiness problem of languages of DFAs.
I would like to see some research articles on ...
5
votes
2answers
130 views
Why do DFAs with a single final state have less power?
I came across this question in a test and I had to answer whether it is true or false.
DFA with single final state has the same powers as DFA with more than one final state.
I was confused by what ...
2
votes
2answers
71 views
Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L
I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.
PROBLEM STATEMENT:
For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = ...
1
vote
1answer
22 views
is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.
1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
2
votes
1answer
36 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
1
vote
1answer
26 views
DFA that accepts strings with last character being repeated at least 1 time before
I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.
Everyway im trying, i get so many ...
0
votes
1answer
77 views
Is this concatenation of two FA done right?
$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider ...
-1
votes
1answer
25 views
Is it possible to create a regular language from an non regular language? (details inside)
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?
say L is irregular, if we add or remove finite number of ...
1
vote
1answer
77 views
Exactly what is the difference between Finite Automata and Transition Graphs?
I haven't found a good enough answer by googling. Here's what i know:
TG's can have more than one initial state
In TG's, Edges/transitions can be labelled with strings
In TG's, it is not necessary to ...
2
votes
2answers
302 views
Language of all strings that has exactly 1 triple b
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
1
vote
1answer
18 views
Number of states in DFA equivalent to given NFA
Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?
1
vote
1answer
26 views
Determining initial and final states from FA diagram
I am new to automata. And learning to find concatenation of two FAs. But this one has confused me
I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
1
vote
1answer
25 views
Trouble understanding this proof about the minimum number of states of a deterministic finite automaton
So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding ...
0
votes
1answer
47 views
regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$
$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$
For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, ...
1
vote
1answer
46 views
Relationship between Deterministic Finite Automata languages
What this "⊃" superset means? What do I need to prove here. Can someone, please, explain in English?
Do I need to do a cross product?
Plus, in textbooks and online I only see "∩" "∪" these kinda ...
0
votes
0answers
13 views
Regex engine: A polynomial algorithm for backreferences?
During my search for a way to integrate efficiently backreferences (using backtracking) into a text-directed regex engine, I found a paper entitled Extending finite automata to efficiently match Perl-...
1
vote
0answers
26 views
Extending Thompson's NFA algorithm with backreferences
I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
1
vote
1answer
15 views
Automaton without variables and guards for queueing system
Disclaimer: Assignment question.
I am trying to solve the below question, the condition is not to use guards and variables. Is it at all possible to do this?
My approach was to have 4 separate ...
0
votes
1answer
80 views
How can I make automaton that has given language? [closed]
I am trying to solve above question, below is the automaton I came up with:
Is there any ways to define automaton without having marked states?
0
votes
0answers
26 views
First part of L=L(A) proof (L(A)⊆L) proves that “δ̂(p,w)=p⇒w has even number of 1s,” so does second part (L⊆L(A))'s use depend on first part's use?
For this proof problem ( https://www.docdroid.net/IcdzSBt/theproblemanditssolution.pdf ), which includes its solution, does the "δ̂(p, w) = p ⇒ w has even number of 1's" from the second part (L ⊆ L(A))...
1
vote
2answers
43 views
What to do with empty set during NFA to DFA conversion?
I am currently converting this NFA to a DFA
I have come up with the following DFA:
...
2
votes
1answer
56 views
Why does the concatenation operation imply the empty string?
I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular ...
5
votes
3answers
201 views
DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$
Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$.
I don't see how it is possible? Because it's a DFA and the alphabet only ...
1
vote
1answer
51 views
FSA for $(ab)^*(cb^n)^*$ [closed]
How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?
An automaton can easily be drawn for the part $(ab)^*$, but the part $(...
0
votes
0answers
16 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
1
vote
1answer
78 views
Context Free Grammer and PDA (Palindrome but without characters repeating in a row)
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says
"L contains palindromes that don’t ever have the same character occur twice ...
3
votes
1answer
50 views
Do multiple transitions over the input give finite state machines more power?
In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state ...
1
vote
1answer
37 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
