Definition of the "DFA for a language"
I just started learning Theory of Computation this semester and a bit confused by the phrase "DFA for a language". If it is asked to construct a DFA for some collection of binary strings L, does it mean to find DFA M with L(M)=L or just $L(M)\supset L$?
Most compiler/theory courses tend to have different styles surrounding teaching definitions of deterministic finite automata and formal languages, but I'll try to make this description as agnostic as possible.
The phrase "DFA for a language" loosely means: a DFA which accepts every word in the language and rejects every word not in the language.
The way I was taught DFAs is to have final/accepting states and regular states which removes the necessity for an implicit error state.
This means that a DFA accepts a word if the state it is in at the end of input is accepting and it rejects the word if the state is not accepting.
Ex:
Let's define L as the language which contains an even number of 1s. These will be binary strings so the symbols are just 0 and 1.
00, 110, 1111111, etc are examples of words in this language. Notice that the empty string is in this language.
We can have two states in our DFA. The starting state, let's call it even 1s, is also an accepting state because 0 ones is even. The other state is odd 1s, this is not accepting.
As for transitions, when even 1s receives a 1, it transitions to odd 1s. And when odd 1s receives a 1, it transitions to even 1s.
Now, the number of 0s doesn't matter, so in either state, it transitions to itself.
Apologies for the double arrow, this website is great but I couldn't figure out how to separate the transitions between even 1s and odd 1s
- Turing Machine for {XF*X|F)*
- Does C# include finite state machines?
- Create a DFA that contains "11" or ends with "10"
- Regular expression for L = {w|w doesn't contain the substring 110} over the alphabet Σ = {0,1}
- Find a finite automata that for the language L={0,1,2} | needs to include 1002 1,2 are odd and 0 is even
- a challenging finite automata - what is the language?
- Am I correct? (Finite Automata)
- Automaton that recognizes a language without 3 consecutive zeros
- Conversion of NFA having a missing transition for any input character on initial state to DFA
- Finite Automata string not ending with ba
- How do I make a string validator for Deterministic Finite Automata?
- Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
- How useful is Turing completeness? are neural nets turing complete?
- NFA or DFA accepting # of positions of 4k between 0's
- How should one proceed to prove (or find) if two regular expressions are same or equivalent?
- Minimum number of states in a DFA having '1' as the 5th symbol from right
- Writing the production rules of this finite state machine
- what is the meaning of {} in the regular expressions {a + ab}*
- What is a finite state transducer?
- Design DFA accepting decimal strings divisible by 7
- How to draw the FA or NFA of b*(ab)*a*
- Difference between transition diagram and finite automata
- What is the application of automata?
- How can I construct finite automata
- Why is {a^nb^n | n <= 10} regular?
- What is the benefit of minimizing a finite automata?
- Complement of non-deterministic context-free language
- Creating a deterministic finite automata
- Can I use stack in Turing Machine?
- Definition of the "DFA for a language"