I am asked to produce a pushdown automaton (PDA) to ensure there are an equal number of 01 substrings as 10 substrings, and likewise that there are an equal number of 00 substrings as 11 substrings.
Heres the problem:
Let L1 ⊆ {0, 1}* be the language of strings that have the same number of 01 substrings as 10 substrings, and the same number of 00 substrings as 11 substrings. (Note: 000 has two 00 substrings) Produce a pushdown automaton that recognizes the language L1.
So far I have tried producing a CFG, which could be later converted to a PDA. No luck there, since I can't seem to produce a CFG to ensure both conditions are met.
I tried many CFG variations of grammar rules similar to:
S -> 00S11S | 11S00S | 01S10S | 10S01S | 010S | 101S | 00110S | ϵ
I've also tried storing each occurrence of 01,10,00,11 as A,B,C,D respectively in the PDA stack. I naively thought I could match and pop A's with B's and C's with D's, and any remaining characters would alert me of not fulfilling the conditions.
Could anyone provide a hint as to steer me in the correct direction?
