Are my DFA's correct? (arbitrary long sequence of 0's and 1's)
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 and ones that ends with a zero followed by a zero or a one.
b) An arbitrary long sequence of zeros and ones that starts with a zero and ends with a one.
These are my DFA's:
They are nearly the same (except the accepting states) and I wanted to know if they are correct? Maybe I'm missing something?
I tried to draw two DFA's. They seem to accept the languages but I think also some more... is that avoidable? Or still correct?
First DFA
Your DFA for the first language has only accept states, and accepts all sequences of 0 and 1. For instance, it accepts any string that has no zeroes, yet we need the one-but-last input symbol to be a zero...
For the first language you'll need four states:
- 𝑞0: did not encounter a
0in the last two reads. This is also the start state, but it is not an accept state. - 𝑞1: the last symbol was
0, but not preceded by a0. So it is not an accept state. - 𝑞2: the last two symbols were
01. An accept state. - 𝑞3: the last two symbols were
00. An accept state.
It looks like this:
Second DFA
Your DFA for the second language will accept "1", which does not obey the rule that it should start with "0". Also, if an input starts with "1" there is nothing that can follow in that input that can make it accepted, so you need a "sink", i.e. a state that is not an accept state and from which you cannot transition to another state.
Again, we need four states:
- 𝑞0: The start state.
- 𝑞1: The input started with
0, and the last symbol so far is a0. This is not an accept state. - 𝑞2: The input started with
0, and the last symbol so far is a1. An accept state. - 𝑞3: The input started with
1, so it cannot be accepted, no matter what follows. This is a sink.
It looks like this:
- Are my DFA's correct? (arbitrary long sequence of 0's and 1's)
- Understanding (and forming) the regular expression of this finite automaton
- Text between two characters
- Regular expression for L = {w|w doesn't contain the substring 110} over the alphabet Σ = {0,1}
- Whether this is the general approach for making a DFA for accepting prefix language of a given regular language?
- Is the language {0^n 1^n 0^k | k != n} context free?
- Automaton that recognizes a language without 3 consecutive zeros
- How to write a generical REGEX expression to: Σ = {a, b, c}, L = {w ∈ Σ ∗ / the first symbol of w is equal to the last symbol of w}?
- How can I allow a single space in a regex in Dart but allow other characters to be 1 or more?
- Which programming languages have a regular grammar?
- Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
- Why is {a^n a^n | n >= 0} regular?
- Is this languages REGULAR / CONTEXT FREE but not REG / Nothing?
- Need simple regex (regular expression) for dynamic expression
- Regular expression for [a-zA-Z]
- Regular expression without "Double or more" spaces
- Split a string by punctuation marks (.!?;:) while excluding abbreviations
- How should one proceed to prove (or find) if two regular expressions are same or equivalent?
- Why do we use pumping lemma to prove the non-regularity of languages? WHY?
- Regex to Detect Zalgo
- Regex-How to prevent repeated special characters?
- Closure property of regular languages under concatenation and star operation
- Using string of set length with pumping lemma to prove irregularity
- Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language
- Regular expression for the following condition
- Checking a string with a regular expression
- Are there any languages such that they are proper subsets of each other and satisfy these conditions
- Given a binary alphabet {0,1}, write a regular expression that recognises all words that have an even number of ’1’s and starts and ends with a ’0’
- Validating a url path with regex and excluding special characters
- Explain regular expression in Python