585
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 ...
1
vote
1
answer
44
views
Regex to DFA question, don't understand why it is this way
I've been dealing with problem 10 on Leetcode (Regular expression matching), where you are supposed to write a program that matches strings to a given regex.I wrote a solution in C that had passed 308 ...
-3
votes
1
answer
50
views
Are my DFA's correct? (arbitrary long sequence of 0's and 1's) [closed]
For my exercise I'm supposed to create two DFA's.
The task specifically is:
Construct a DFA over the alphabet Σ={1,0} accepting the following regular languages.
a) An arbitrary long sequence of zeros ...
0
votes
1
answer
106
views
Create a DFA that contains "11" or ends with "10"
I'm trying to construct a DFA (binary only) that contains "11" or ends with "10".
I tried to do the following:
$q2$ and $q3$ are accepting states
State
0
1
$q0$
$q0$
$q1$
$q1$
$...
0
votes
0
answers
37
views
How can we use the ltlf2dfa tool to convert a temporal formula with predicate form into a DFA ?
We know that LTL divided into DFA can transform an LTLf formula into a DFA, but when in the context of intelligent planning, the general LTLf formula expressing the timing goal will contain some ...
0
votes
1
answer
41
views
How do I restrict the allow keys of an object with Typescript generics?
I want to only allow one type of object as function parameter. Object keys must start with $, only contain alphabetical characters, and its values must be of type Test. Under "example 1" ...
0
votes
1
answer
154
views
Regular expression of "odd number of a and odd number of b"
I want to create a regular expression of odd lengths of a and b. I found this solution on Stack Overflow:
((a+aaa)*(b+bbb)*(a+aaa)*(b+bbb)*(a+aaa)*)*(ab+ba).........
I found it to be correct from ...
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
91
views
a challenging finite automata - what is the language?
I have this finite automata (FA) and want to write its language. I think its
L={x E {0,1} | {x with subset of 00 and ends in 1} and it would help to know what the type of FA it is.
I think it's a DFA ...
2
votes
2
answers
71
views
Correct labeling for this regular language?
So I am a newbie computer science person and would like some help from the community in helping me understand this subject.
I have this regular language I am trying to determine is 3 things from this ...
1
vote
1
answer
240
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 . (...
1
vote
0
answers
19
views
How to get automatically token for dfa every 7 days
I have DFA accounts.
I have about 1100 profiles and accounts
I can't use the service account
So, I am using the token that expired after seven days.
I replaced the token every week by myself.
My ...
0
votes
0
answers
35
views
Finite state automata minimization
I'm trying to model a software agent with these specifications: it simulates a labeling robot that has to label three box that are identified by the positions 1, 2 and 3, he cannot label the same box ...
2
votes
1
answer
2k
views
DFA for all binary strings having even number of 0's or contains exactly two 1's
I'm trying to solve this challenge:
Design a DFA for all binary strings having an even number of 0's or containing exactly two 1's
I'm a bit confused with this question. I had tried to come up with ...
0
votes
1
answer
187
views
Need a DFA for the alphabets {a,b} such that the language must contain equal and even numbers of a and b
The DFA for even numbers of and b is this DFA for even numbers of a and b but the DFA of even and equal number of a and b is not available
L={\epsilon,aabb,abab,baba,bbaa,aaaabbbb,aabbaabb,bbaabbaa,...
0
votes
0
answers
69
views
Intersection of two Deterministic Finite Automata (DFA)
I am looking for a method to make an intersection of two automata. As each language is a set of strings and the intersection operator is a defined one in the context of sets, and each language has a ...
0
votes
0
answers
13
views
Assembly Code Segmentation Error While Making DFA state machine [duplicate]
I have the following code:
.section .data
input_prompt:
.asciz "Enter a string of 0s and 1s: "
invalid_message:
.asciz "ERROR: invalid input\n"
EEPrompt:
.asciz "Input ...
0
votes
0
answers
47
views
Deterministic finite-state automaton in x86 Assembly (GCC)
I'm working on a DFA program in Assembly. This is basically a system that reads a binary string and interprets them in the following states, shown in the below image.
It essentially just shows the ...
0
votes
1
answer
128
views
Construct DFA that accept binary string having odd number of 1’s or even number of 0’s
The question I have been asked is "Design a DFA accepting the set of all strings with an even number of 0’s and an odd number of 1’s on the alphabet {0, 1}."
Is it correct or wrong. please ...
-2
votes
1
answer
60
views
What strings are accepted by the pattern "^[ab]?|c?$"?
What I have gathered till now:
^ -> match the first symbol
$ -> match the last symbol
[] -> set of characters that can be in the position
| -> the "OR" operator
? -> the ...
-2
votes
1
answer
50
views
Does this DFA satisfy the complement of the given language?
I got this challenge:
Given 𝐿 = { 𝑤 ∊ {0, 1}* : 01 is a substring of 𝑤 }
Show 𝐿 compliment is regular.
My understanding is that a DFA for the compliment of this language would need to reject 01 ...
0
votes
0
answers
89
views
Lexical Analyzer with table-driven and character classification in rust
I am writing a lexer for C language as an exercise in Rust, for now I succedded implementing a lexer using backtracking, as follows:
lex_keyword(input)
.or_else(|| lex_identifier(input))
.or_else(|| ...
0
votes
1
answer
729
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
0
answers
21
views
Ned help drawing a dfa from this hypothesis?
This DFA accepts any string over the alphabet {a, b} where the number of 'b's, if present, is even. An example of strings it accept:
Accepted:
a
aa
bb
aaa
abb
bab
bba
aaa
abb
bab
bba
aaaa
aaab
aabab
...
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 ...
0
votes
1
answer
152
views
DFA for complement language of given language
We have a language W over the alphabet {a,b,c,d,e,f,g} that is defined by, starting with :
<A> ::= <A> <Z> 'c' | <A> <X> 'd' | 'b'
<Z> ::= <Y'> 'e' <Z> |...
-2
votes
1
answer
823
views
converting from dfa to regular expression
Can someone explain to me how to convert this DFA to a regular expression?
I have tried using Arden’s theorem but I don’t know how to simplify the equations to get the regular expression for this DFA. ...
2
votes
0
answers
122
views
Finding Myhill-Nerode relation to get equivalence classes
Fix strings x and y, |x| < |y| = n. For any 2 strings of different lengths, there is a DFA with O(logn) states that accept x and rejects y. Prove that this DFA exists.
My approach: I tried to find ...
1
vote
1
answer
630
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
87
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 ...
0
votes
1
answer
266
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 ...
-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
votes
2
answers
148
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
261
views
Given a DFA with multiple Final states. How can I find its compliment?
It is not possible to have multiple start state in DFA but how can I achieve Compliment operation on DFA having multiple Final states?
I try Complimenting the language of given DFA but how multiple ...
2
votes
1
answer
90
views
Complement of a given Language for a DFA
For DFA, the alphabet Σ = {a,b} the language this DFA will recognise is {w|w must contain a}. For this language that the DFA recognises, what would be the compliment of this language or how would it ...
1
vote
1
answer
52
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
607
views
Why the conversion of an NFA to DFA is 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 the NFAs
DFAs are easier to ...
-1
votes
1
answer
355
views
How to construct DFA that L accept : w contain '110' and doesn't contain '010'?
L = { w belongs {0,1}* | w contain '110' and doesn't contain '010'}
I need to construct DFA that receives L.
How can I draw a DFA that will do the both of conditions?
hints will be a great help.
-2
votes
1
answer
506
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
vote
1
answer
46
views
How can I make the DFA respect the final states?
I wrote the code of a DFA for a class. It accepts or refuses certain inputs correctly such as strings x = abbaaa, y = baba, z = abaaabaaab. What i want to solve is, whenever a smaller string inputs ...
-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
1
answer
422
views
TypeError: validate() takes 1 positional argument but 2 were given (Automata lib)
Can someone help me with this error, i have spend more than an hour and got nothing
Lib: https://pypi.org/project/automata-lib/
Here is the TypeError and as you can see im only giving one argument and ...
0
votes
0
answers
40
views
how to block sensitive words, but exempt if sensitive words follow with particular words
I am using DFA(deterministic finite automaton) for blocking sensitive words in a paragraph, but I meet with a problem is that:
for example, I want to block "I love", but if I love along with ...
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
274
views
NFA-lambda to DFA conversion
Can somebody help me to convert this nfa-lambda to dfa?
2
votes
0
answers
91
views
Why text-based regex engines cannot handle lazy quantifiers?
I have came across many times that, text-based regex engines cannot support lazy quantifiers. But I could not find why. But I came to know that, they internally use DFAs, and they do not backtrack.
...
1
vote
2
answers
497
views
How to find longest accepted word by automata?
I need to write a code in Java that will find the longest word that DFA accepts. Firstly, if there is transition to one of previous states (or self-transition) on path that leads to final state, that ...
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 ...
1
vote
1
answer
262
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 ...