FA that accepts odd 1's and ends with 101

Question

I have been trying to come up with a FA that accepts odd 1's and ends with 101, also leading zeros are allowed. So far I have this.

Problem is as you can see it fails with the string 000010000100010101 which has odd number of 1's and ends with 101. I tried to combine odd 1's and 101 string FA to get this but it doesn't work. So either I am combining them wrong or I shouldn't combine them at all.

Are you trying to make a deterministic or nondeterministic FA? — Q the Platypus, Mar 03 '19 at 23:10
Do you know how, given two FA $A_1$ and $A_2$, you can make a third FA that accepts a given string iff $A_1$ and $A_2$ both do? — Aphelli, Mar 03 '19 at 23:12
@Mindblack I thought you could do A1{S1,S2}xA2{S1,S2} but this is what I got doing that. — afb, Mar 03 '19 at 23:16
Looks like your construction is faulty then. Here should be a description: https://stackoverflow.com/questions/7780521/how-to-use-the-intersection-construction-to-form-a-dfa . — Aphelli, Mar 03 '19 at 23:20
@Mindlack does this work with nfa as well or is it only dfa-dfa. — afb, Mar 03 '19 at 23:33

score 1 · Answer 1 · answered Mar 04 '19 at 09:00

In other words, your language consists of strings with an odd number of $1$ followed by $101$ (because $101$ does not change the "oddity" of the number of $1$s). So you do not need to run two automata in parallel, but rather can run them sequentially.

In your start state the number of $1$s is even, add another one for an odd number of $1$s. From the latter one, add a (non-deterministic) transition reading $1$ to the corresponding state in the automaton for $101$, i.e. its state after reading the first $1$.

If this description is too rough, I can provide more detail.

FA that accepts odd 1's and ends with 101

1 Answers1