Questions tagged [dfa]

A DFA is a deterministic finite automaton, a simple model of computation. It is one way to model regular languages. Each DFA consists of a finite set of states and a transition function between those states describing how the state of the machine changes in response to new input. DFAs are closely related to regular expressions in the sense that they can be converted into each other. Thus, DFAs are often used to implement regular expression matchers.

dfa
Filter by
Sorted by
Tagged with
3 votes
1 answer
197 views

Is this transformation from a NFA to a DFA correct?

I am studying for an exam and came up to this task in the picture usually the transformation from a NFA to a DFA is easy to me. I create a transition table from the NFA and for every "new" combined ...
6 votes
2 answers
2k views

How can I simplify token prediction DFA?

Lexer DFA results in "code too large" error I'm trying to parse Java Server Pages using ANTLR 3. Java has a limit of 64k for the byte code of a single method, and I keep running into a "code too ...
1 vote
1 answer
447 views

Rules to convert a CFG to a NDPA?

I have to define an FA by using this grammar: S -> aSb S -> c S -> dA A -> Sd How do I manage the first rule and the last one? For the second one I think I have to create another state (...
7 votes
2 answers
724 views

Minimize a DFA with don't care transitions

I have a DFA (Q, Σ, δ, q0, F) with some “don't care transitions.” These transitions model symbols which are known not to appear in the input in some situations. If any such transition is ...
0 votes
1 answer
82 views

c program about grep

im having trouble with this code ,its about search string from file after converting to dfa and nfa whenever i try to access argv value, it give " 0x7fffffffe977 "XDG_MENU_PREFIX=gnom"... " maybe ...
1 vote
1 answer
2k views

find a regular expression for the language accepted by the following automata

Find a regular expression for the language accepted by the following automata. Eliminate q1 q0: ab q2: ba* q0 to q2: b+aa q2 to q0 : bb Eliminate q2 q0: ab+b+aa(ba)* (not sure if my way is ...
-1 votes
1 answer
228 views

Designing a DFA

I want to design a DFA for the following language after fixing ambiguity. I thought and tried a lot but couldn't get a proper answer. S->aA|aB|lambda A->aA|aS B->bB|aB|b
0 votes
1 answer
103 views

NFA to DFA conversion confusion?

I have this NFA in the book given: And their solved DFA result was this: But According to my solved solution (by finding e-closure of each state), it looks something like this: | a | b | c ...
0 votes
1 answer
1k views

How to define accepting states in a finite automation?

I can build a finite automation from a dataset and would be glad to expand that to a deterministic finite automation (DFA). A DFA requires accepting states. How one can identify them, or how these can ...
0 votes
1 answer
375 views

Construct a Deterministic Finite Automata (DFA) for the language 1*01 (11)*(0 U 1)*,

Construct a Deterministic Finite Automata (DFA) for the language where the set of all strings are of the form 1*01 (11)*(0 U 1)*, that contain 01 as a substring
1 vote
0 answers
88 views

Is this an error from book <Introduction to the Theory of Computation>?

The book <Introduction to the Theory of Computation>(3rd), described a NFA: Then feed input '010110' to this NFA, the book gave this tree which I think is wrong: The second input symbol '0' goes ...
1 vote
1 answer
362 views

Convert the given NFA

Question) Σ={a,b} and NFA is given in the following figure: Using the procedure NFA to DFA, convert given NFA to DFA. Using the reduce procedure, minimize the states in the DFA I did a transition ...
0 votes
1 answer
440 views

RegEx for transforming a path graph

Pretty much we are asked to find a regular expression for the DFA as shown in the link attached above. What I've gotten down is the path from s0 to s2 which I think is (a(b(ab)) and s0 to s4 which I ...
0 votes
0 answers
31 views

How to distinguish delimiter for different states in scanner-generator?

I have implemented a simple Scanner-Generator. I am experiencing one problem during making, it's about the delimiter classification. For example, if a white-space is included, such as "a + b", you ...
0 votes
0 answers
225 views

How to minimize DFA having multiple accept nodes?

I have implemented a simple Scanner-Generator, which runs properly in all situations. It's not a code issue, but a question about how to optimize DFA. Minimization for one Accept Node using the ...
0 votes
1 answer
239 views

Prove that the following language is regular:

Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA. Prove that the following language is regular, by making an appropriate NFA for it: 𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎...
1 vote
1 answer
377 views

DFA in Scheme (homework)

Working on a homework question asking to write a DFA-acceptor in Scheme. Alphabet: {0, 1} Start-state: {Q0} Final-state: {Q2}. String must have a 01 in the sequence to be accepted. States: Q0 on 1 ...
0 votes
1 answer
148 views

Determine the language describe by the CFG

S -> 1A A -> 0B | 1A | epsilon B -> 0C | 1B C -> 0A | 1C I was thinking that the language described by this grammar is the following: L = {0,1 | w string contains 1+ OR it has at least ...
-6 votes
3 answers
212 views

Regular expression [ 1 ( 0 1* 0)* 1 ]* DFA

What are the conditions for the chain to be accepted by this regular expression?
0 votes
1 answer
224 views

Is my description of the language accepted by this DFA?

Image of DFA: https://ibb.co/LCW99q9 From my understanding, any string is accepted as long as it contains the substring “abc”; anything before is okay, and everything after is okay, including “λ”. My ...
9 votes
3 answers
7k views

self-taught compiler courses / good introductory compiler books?

Does anyone know of online course / university lectures that comprise a typical compiler course? I've had theory of computing but unfortunately my school didn't offer a course in compiler ...
1 vote
2 answers
7k views

State Elimination DFA to Regular Expression

I have a few questions regarding state elimination and the terminology. In the example above is a DFA with a accepting state where you must start with symbol 0 and end with 1. If I were to convert ...
2 votes
2 answers
158 views

Given Two Regex, Determine if One is a Complement of Other

I'd like to know how you can tell if some regular expression is the complement of another regular expression. Let's say I have 2 regular expressions r_1 and r_2. I can certainly create a DFA out of ...
1 vote
2 answers
1k views

Equivalence between regular expressions

I have two different regular expressions: (1) ($ + b)a*(b + bba*)* ($ is the empty language) (2) b*(a + bb + bbb)*b* I want to demonstrate that both expressions are equivalent, but I don't know how....
2 votes
2 answers
321 views

Regular expression over the language C={a,b}

Good evening everyone,i'm getting stuck with the following regular expression, I think there is a much easier approach to the expression than mine, I had to writing down the regular expression and ...
1 vote
0 answers
868 views

Given two DFA's, how can I check that the language generated by the first DFA is included in the one generated by the second one?

I have to give an algorithm to check whether given two DFA's, the language generated by the first one is included in the generated by the other one. For example, suppose that the first language ...
0 votes
1 answer
1k views

DFA of two simple languages and then product construction of those two languages

The language below is the intersection of two simpler languages. First, identify the simpler languages and give the state diagrams of the DFAs that recognize them. Then, use the product construction ...
0 votes
1 answer
579 views

Generating a regular expression from a language

I need to find a regular expression to define the language of all binary strings with at most one 1 in each substring of length four. Accepted string: 0001000100 Rejected string: 100010100 My ...
3 votes
1 answer
780 views

Haskell program that can handle any arbitrary deterministic finite automaton

𝑄={𝑠0,𝑠1,𝑠2,𝑠3,𝑠4} 𝑞𝑠=𝑠0 𝐹={𝑠3} 𝛿=〈𝑠0,0,𝑠1〉,〈𝑠0,1,𝑠1〉,〈𝑠0,.,𝑠2〉,〈𝑠1,0,𝑠1〉,〈𝑠1,1,𝑠1〉, 〈𝑠1,.,𝑠3〉,〈𝑠2,0,𝑠3〉,〈𝑠2,1,𝑠3〉,〈𝑠2,.,𝑠4〉,〈𝑠3,0,𝑠3〉,〈𝑠3,1,𝑠3〉, 〈𝑠3,.,𝑠4〉〈𝑠4,0,�...
1 vote
1 answer
900 views

How to parse an input string for matches given a DFA

I'm implementing a regular expression parser from scratch by generating a NFA from a regular expression and then a DFA from the NFA. The problem is DFA only can say when a computation is accepting. If ...
1 vote
1 answer
392 views

Is it TRUE that L^R = L, if and only if L is the language of palindromes?

S1: LR = L, if and only if L is the language of palindromes. where LR is obtained by reversing all the strings of L. Is S1 TRUE?
1 vote
1 answer
65 views

Compiler Construction - Why does some tokens requires a final state with a backtrack?

So i'm studying compiler construction for an exam , but there seems something i can't understand. Let's assume the following set of terminals: T = {:, *, =, (, ), <, >, {, }, [a..z], [0..9]} ...
2 votes
1 answer
445 views

Deterministic Finite Automata divisibility problem

Design a DFA that accepts the string given by L = { w has number of 'a' divisible by 3 and number of 'b' divisible by 2 over the alphabet {a,b} }
88 votes
3 answers
188k views

Design DFA accepting binary strings divisible by a number 'n'

I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'. There will be different DFAs for different 'n'...
0 votes
2 answers
2k views

Can a DFA be designed to accept any language?

The answer given by our instructor to this question is FALSE. However, I think it has to be true. Take this DFA that accepts sigma star. Q -> {s_1} q_0 -> s_1 sigma -> {a, b} F -> {s_1} delta -> {...
0 votes
1 answer
205 views

DFA delete not acceptable characters

So i represent this DFA: Like this initial(0). final(2). arc(0,a,1). arc(0,b,0). arc(1,a,1). arc(1,b,2). arc(2,a,2). arc(2,b,2). And i have a predicate that parse a string and returns true if is ...
2 votes
1 answer
113 views

How to write this automaton

I am trying to solve some problems in An Introduction to Formal Languages and Automata, by Peter Linz. In Section 2.1 (Deterministic Finite Acceptors), I cannot write the automaton and need help to ...
2 votes
1 answer
135 views

Formulation of language and regular expressions

I can't figure out what is the formal language and regular expression of this automaton : DFA automaton I know that the instance of 'b' or 'a' have to be even. At first I thought the language was: ...
7 votes
1 answer
7k views

time complexity trade offs of nfa vs dfa

I am looking for a discussion on which is better used and in what circumstances in a compiler an nfa or dfa. what are the time complexity trade-offs of simulating an nfa vs dfa and which one is more ...
0 votes
1 answer
500 views

Showing that the intersection of two language accepted by NFA is undecidable

I am having problem with this problem. Let A = {〈N1, N2〉 | N1 and N2 are NFAs and L(N1) ∩ L(N2) =∅}. Show that A is decidable. Any help is appreciated.
1 vote
1 answer
2k views

When do Turing Machines have final states?

This may be a silly question, but when do Turing Machines have final states exactly? I see some with final states and some without, I'm a little confused right now.
-1 votes
1 answer
219 views

DFA for (0001)*, is it correct

PLease check whether this dfa is correct or not? Thankyou
1 vote
1 answer
273 views

How to create a DFA union transition dictionary based on transitions of DFA1 and DFA2

I have 2 DFA's, the transitions of which look as follows: DFA1 {('q0', 'a'): 'q1', ...} DFA2 {('q0', 'a'): 'q3',...} As I understand, the delta of the unified DFA is supposed to look something ...
-4 votes
1 answer
11k views

Designing DFA to accept language of even length beginning with 11 [closed]

Design a DFA to accept language L={w|w is of even length and begins with 11} where inputs are 0'a and 1's?
0 votes
0 answers
73 views

Take use input in sets and Dictionaries (Python)

class DFA: current_state = None; def __init__(self, states, alphabet, transition_function, start_state, accept_states): self.states = states; self.alphabet = alphabet; self....
2 votes
2 answers
7k views

What will be the DFA for the regular expression 0(0+1)*0+1(0+1)*1?

This is the DFA i have drawn- Is it correct? I am confused because q4 state has 2 different transitions for same input symbol which violates the rule of DFA, but I can't think of any other solution.
-3 votes
1 answer
169 views

Please help me covert the dfa to regular expression [closed]

i don't know how to use algorithm to covert this dfa to regular expression. Please help me.
3 votes
1 answer
7k views

DFA without final state

We can have a Deterministic Finite Automata (DFA) without final state. Whether it's meant! What is the meaning of a Deterministic Finite Automata (DFA) without final state? Thanks
0 votes
1 answer
150 views

Deterministic finite automaton (DFA) accept strings

Construct a DFA that accept the following string A(B|(BC+))*C , i do not understand the sequence of the string really well
0 votes
1 answer
639 views

What if all states are accepted in Minimizing Deterministic Finite Automata with Hop-croft Algorithm?

Here we have a DFA like this: Is this already a minimized DFA or should we minimize it using Hopcroft algorithm by grouping all accepted states in one class and output:

1
3 4
5
6 7
12