Skip to main content
Filter by
Sorted by
Tagged with
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 ...
txblx's user avatar
  • 1
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 ...
adlibbinbitch's user avatar
-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 ...
Auxelia's user avatar
  • 11
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$ $...
Salty Champ's user avatar
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 ...
Solya's user avatar
  • 1
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" ...
msbb's user avatar
  • 53
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 ...
sachin yadav's user avatar
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", &...
DaneShuler's user avatar
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 ...
DaneShuler's user avatar
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 ...
cool cat's user avatar
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 ...
cool cat's user avatar
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 . (...
Thien An's user avatar
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 ...
Gil Nathan's user avatar
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 ...
sunbrotta's user avatar
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 ...
just coding's user avatar
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,...
SOURAV's user avatar
  • 1
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 ...
Ehsan's user avatar
  • 1
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 ...
Erique's user avatar
  • 57
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 ...
Erique's user avatar
  • 57
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 ...
Muhammad Manik Uddin's user avatar
-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 ...
kesarling's user avatar
  • 2,112
-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 ...
sukhi's user avatar
  • 11
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(|| ...
Matrix22's user avatar
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 ...
Kush_Uttam's user avatar
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 ...
Kinglouis01's user avatar
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 ...
mindoverflow's user avatar
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> |...
phuck's user avatar
  • 23
-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. ...
amanda che's user avatar
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 ...
Charlie's user avatar
  • 121
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. ...
mark's user avatar
  • 81
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 ...
Pouya Kafashi's user avatar
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 ...
mark's user avatar
  • 81
-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
coding12's user avatar
-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 ...
NEEDhelpWITHthisQ's user avatar
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 ...
Anubhav Tyagi's user avatar
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 ...
ali_m's user avatar
  • 21
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 ...
Lorenzo's user avatar
  • 19
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 ...
user20183430's user avatar
-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.
AndrewM's user avatar
  • 55
-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 ...
Apriana's user avatar
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 ...
JPtheOne's user avatar
-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, ...
user19187727's user avatar
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 ...
gfts_16's user avatar
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 ...
greenhand96's user avatar
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 ...
sandbuzzard's user avatar
0 votes
1 answer
274 views

NFA-lambda to DFA conversion

Can somebody help me to convert this nfa-lambda to dfa?
mmbnn's user avatar
  • 9
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. ...
Sourav Kannantha B's user avatar
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 ...
qu4lizz's user avatar
  • 339
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 ...
qu4lizz's user avatar
  • 339
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 ...
Teo's user avatar
  • 43

1
2 3 4 5
12