309
questions
0
votes
0
answers
28
views
Python: Processing regex into DFA - logic to handling the transitions correctly
So i have all the elements and the programm runs. However ive been stuck for 2 weeks on the point of NFA conversion. I cant seem to get the logic right for:
concat (moving states without using extra ...
0
votes
1
answer
26
views
Theory of Comp Sci - State Diagrams NFAs
1.49 Theorem
Here is a correct example:
As here is an example for one that is correct:
prob_1_10c = NFA(
states={"q0", "q1", "q2"},
input_symbols={"0", &...
0
votes
1
answer
78
views
Theory of computer science problems
I am working on theory of computer science problems but cannot get these to work:
a. Give an NFA recognizing the language (01 ∪ 001 ∪ 010)*
b. Convert this NFA to an equivalent DFA. Give only the ...
1
vote
1
answer
256
views
State diagram of DFA with 5 states
Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F . (...
0
votes
1
answer
754
views
Conversion of NFA having a missing transition for any input character on initial state to DFA
I was practicing NFA (Non-Deterministic-Finite-Automata) designing and converting them to DFA.
Then suddenly I got a doubt, as all the examples I have seen for conversion had NFA's initial state with ...
0
votes
1
answer
1k
views
Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
In automata theory, we can use Myhill–Nerode theorem to prove that a language is not regular.
The theorem makes use of the concept of distinguishable and non-distinguishable strings.
While it is ...
1
vote
1
answer
84
views
Create a NFA from BNF grammar
How do I create an NFA from BNF grammar?
What I am specifically stuck on is the fact when we have two cases of recursion in the grammar such as in:
< case > ::= < case > < int > 'b' |...
2
votes
0
answers
217
views
Bitap algorithm for Fuzzy search example
I was looking at this work page 31. It is talking about the Wu and Manber 1992 updated Bitap algorithm for Fuzzy search with Non-deterministic Automata. To be more precise this formula:
Let's also ...
1
vote
1
answer
637
views
DFA- Set of all 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 states.
...
0
votes
1
answer
268
views
NFA or DFA accepting # of positions of 4k between 0's
Left is the given solution, but it fails for 01110(shouldn't be true) and 010000 (should be true). If we do it like the right one like I did, then there might not be 1 in it so it fails because 000000 ...
0
votes
0
answers
25
views
unable to display tables and diagrams in python for non deterministic finite automata
I want to ask for help to solve this problem, I wonder if there is something wrong with my code or are there tools or extensions that I haven't installed
enter image description here
I've tried to ...
-2
votes
1
answer
42
views
By writing a regular expression or a grammar, describe the language accepted by the NFA
NFA diagram
the strings accepted are aaaaa which is pretty clear. The L = (111 + 1111)* is what I am getting but I need it in regular expression or grammar
1
vote
1
answer
53
views
Why is the most constraint language for this not Regular and instead, Context-Free?
This is the question:
Q: Given the following production rules, which is finite or otherwise the most constrained language in the Chomsky language hierarchy corresponding to the language described by ...
0
votes
1
answer
620
views
Why is the conversion of an NFA to DFA useful?
Can someone tell me some reasons why the conversion of an NFA to DFA is useful?
Until now I have found the following reasons (I am not sure of them):
DFAs are faster than NFAs
DFAs are easier to ...
-2
votes
1
answer
510
views
Regular Expression | Automata Theory
does anyone know about regular expressions of the following languages:
the set of all strings starting with 000 and not ending 11
the set of all strings with odd string length and ending in 111
L6 is ...
-1
votes
1
answer
143
views
Why doesn't {a^nb^n | n >= 0} follow regular language closure properties?
Using the pumping lemma, we can prove that {a^nb^n | n >= 0}, but what is not clear is the following.
{a^n | n >= 0} is regular by itself and so is {b^n | n >= 0}, and if I am not mistaken, ...
0
votes
2
answers
3k
views
NFA for the star of a language (01 U 001 U 010)*
Problem from page 5 of this pdf.
Give an NFA that recognizing the language (01 U 001 U 010)*
I think this is wrong because there should be an additional start state (accepting) going to state 1 for ...
1
vote
0
answers
53
views
How this state set of DFA was retrieved from the given NFA
I have this NFA:
1,{2, 3}
2,empty
3,{4}
4,empty
All the arrows in this NFA are epsilon-arrows.
I understand that all possible states that can be reached from each of the states, using only epsilon ...
0
votes
1
answer
290
views
NFA-lambda to DFA conversion
Can somebody help me to convert this nfa-lambda to dfa?
0
votes
1
answer
138
views
NFA for this specific design
I have this NFA bellow, and I feel that it has the regular expression (0+1)*00. But looking at it i also feel that I should add something to the RE for the transition q2->q0, but cant quite ...
1
vote
0
answers
90
views
How would you draw the NFA Language x*?
I am learning about automata, and we are now learning about NFAs, my professor told us to write an NFA for some language x*, as I understands * means that if you also have no input the language should ...
2
votes
1
answer
2k
views
How to apply Kleene star on automata?
I know how to apply Kleene star on language but I'm not sure how would I apply it to DFA or NFA. I'm pretty sure it would need to be epsilon NFA with initial state that is final and final states might ...
0
votes
1
answer
171
views
How can I add an epsilon move to FSM using Python?
I am using the greenery module to implement an FSM:
from greenery import fsm, lego
E, O = range(2)
z, o = '0', '1'
# Create the FSM
machine = fsm.fsm(
alphabet = {o, z},
states = {E, O},
...
1
vote
1
answer
270
views
When minimizing DFAs through table fill, should a pair of final states transition to a final/undetermined(dead) pair be treated as distinguishible?
Here the pair q0q5 is final/final, but their transition through input 1 is to q2/undefined (dead). Would the undefined be considered be considered nonfinal for the sake of marking the x? Logically it ...
0
votes
2
answers
2k
views
A NFA accepting ;anguages whose final digit didn't appear before
Give a non-deterministic finite automata(NFA) which accepts the following language:
The set of strings over the alphabet {0,1,...,9} such that the final digit has not appeared before.
I have ...
0
votes
1
answer
252
views
Store NFA into data structure
I am provided with a NFA and I need to use a data structure (I can not use recursive descent parser) for storing it. Once the NFA is stored in a data structure I am given a string to check if the ...
0
votes
1
answer
458
views
What is the language accepted by this NFA? Can you express it in English and with regular expression?
I have been trying to solve this NFA, this below it is the best I could come up with. I have hard time describing in English the language it produces, can someone help me to understand better?
...
0
votes
1
answer
358
views
How to deal with epsilon transitions while converting NFA to DFA?
The start state(S0) of my NFA has 2 outgoing epsilon transitions to S1 and S2, and, S1 and S2 have further transitions, and are disjoint of each other. So do I consider {S1,S2} as one state while ...
1
vote
1
answer
71
views
CSS "escape" syntax diagram confusion
Have a look at the syntax diagram for the escape language:
I read the second set of transitions as follows:
The state transitioned to by the \ symbol can transition to the accepting state if the next ...
0
votes
1
answer
436
views
Finding an NFA with 2 conditions
I am trying to figure out how to write an NFA which can accept the following language with only 6 necessary states:
{w: number of a's is even OR exactly 2 b's} over the alphabet ∑={a, b}
.
Here is an ...
0
votes
1
answer
175
views
In Non-Deterministic Finite Automata (NFA), how is the next branch/transition selected when there are two or more transitions?
For NFA, when there are 2 or more transition states, how does the machine decide which transition to take?
I was only able to find the "Guess and Verify" methodology, where we consider the ...
1
vote
0
answers
281
views
Program for NFA to accept strings that has atleast one character occurring in a multiple of 3
So there this c++ code for the following question: NFA to accept strings that have at least one character occurring in a multiple of 3.
The problem is it's showing "accepting" as the output ...
1
vote
1
answer
879
views
can a DFA have an arrow with empty string as input?
I've seen a picture of an automata represented as a DFA but it has arrows that has nothing on it!
What do these arrows mean in DFA? I mean are they different from epsilon (ε) , because we do not have ...
-1
votes
3
answers
2k
views
NFA that does not accept strings ending "101"
What is the NFA that does not accept strings ending "101"?
1
vote
1
answer
4k
views
Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter
I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA, but can not ...
0
votes
0
answers
138
views
Find NFA for this language
I've constructed the NFA (non deterministic finite automaton) for this language L = (aa*b) ∪ b ∪ (aab)*
Is it correct? I'm not really sure with the Epsilon-transitions.
0
votes
2
answers
946
views
Why does this helper function give me an unbound value error?
I have a helper funtion which is as follows:
let rec helper2 nfa l symb res =
match l with
| [] -> res
| h::t -> res@(transitions nfa.trans symb h) in
...
1
vote
1
answer
1k
views
Non-Deterministic Finite Automata of {ab, abc}* in Python
I have been trying to draw this Non-Deterministic Finite automaton:
NFA with the number of states not exceeding 3 for the language {ab, abc}*, and I reached the solution in the picture below:
NFA ...
0
votes
3
answers
714
views
Make Transition table for DFA
How to convert this NFA to DFA :
From state [BC] on 'a' is not going to any state hence it is not forming a DFA
0
votes
1
answer
1k
views
Is this NFA correctly accepting inputs that end with a 00?
In a lecture it was said that this NFA accepts inputs ending with two zeros or inputs=0: https://ibb.co/9Wt0j7J .
The alphabet is {0,1}
But if the input would be 001 we would on some path also end up ...
0
votes
1
answer
181
views
Calloc error on struct pointer of pointer
I have a problem with my calloc but i can't figure out why. Here is my code:
void ens_init(ensemble* node, ullong value, uint i){
// *node = malloc(sizeof(struct ensemble)); # Doesn't work
// *...
0
votes
1
answer
76
views
Why do we use pumping lemma to prove the non-regularity of languages? WHY? [closed]
I am currently working on the usage of pumping lemma and I need to know why do we use pumping lemma? the main question asked is why?
I know we can prove the non-regularity and I know the formula/proof ...
0
votes
0
answers
51
views
RE: implemrnting match range {m,n} in NFA?
I was able to using NFA to implement + and ? and ., but I'm having hard time figuring out how to implement match-range {m,n}. F.e.:
a{1,3}
(ab){2,4}
.{,3}
and so on.
Is there a way to implement it ...
0
votes
1
answer
156
views
RegEx that matches "variable" strings/sequences? + backtracking?
I want to use regex like language to match against variable-string (in my case sequence of character|words|numbers stored in a graph DB).
I found a way to implement RegEx engine :
https://deniskyashif....
1
vote
1
answer
2k
views
Convert NFA for email validation into DFA
Can anyone help on how to convert the NFA for this email validation into a DFA?
In order to make the conversion I have first created state transition table, then can any one help to create DFA?
0
votes
1
answer
414
views
Is it possible to compute the intersection of two non completely specified DFA?
If the two DFAs for which the intersection has to be computed are not completely specified, it can happens that it is possible to reach a state containing only one state of the two DFAs. Is that ...
1
vote
3
answers
4k
views
How to draw DFA of language A={w | Every even position of w has symbol 0}?
I need to draw a DFA for a machine. Machine accepts the language A.
Language A={w | Every even position of w has symbol 0} and
Σ = {0,1}.
I drawed the DFA.Not sure if it is correct.
Here is my DFA,
...
0
votes
0
answers
130
views
Is NFA without null transition allowed?
I have made an NFA but have no null transition. is it allowed in NFA? I am creating NFA with generic approach. I am not sure about its correctness. NFA could be any type or is there any particular ...
-4
votes
2
answers
1k
views
Convert This NFA to DFA
I'm having trouble understanding how to convert.
I made a state table for NFA but
This alphabet instead of (a,b) makes me confused.
Can anyone help me how to convert this NFA to DFA?
1
vote
1
answer
558
views
Can you make a DFA/NFA/ Lambda NFA for determining whether a number is prime or not? [closed]
As the title says, is it possible?