1
$\begingroup$

$ L = \{ w ∈\{0,1\}^* \mid |w|_0 = |w|_1 \mod 5 \}$

So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA!

I'm studying for my exam and this was on the book, the book says its CFL but doesn't say whether its DCFL or not and does not draw any PDA for it!

i tried making 5 states and go to the next state everytime i see a 0 {because 0 will always be between 0 and 4} but didn't work

also $|w|_0$ means number of 0's

$\endgroup$
3
  • $\begingroup$ Your language is regular. Regular languages are deterministic context-free. $\endgroup$ Jan 21 '18 at 22:49
  • $\begingroup$ This seems like a RL, you can always maintain the number of 0s and 1s $mod 5$ with a finite number of states, without a stack. $\endgroup$ Jan 22 '18 at 1:08
  • $\begingroup$ Can you give me a hint about how should i make a DFA for this? $\endgroup$
    – John P
    Jan 22 '18 at 5:43
2
$\begingroup$

What does $|w|_0 = |w|_1 \mod 5$ means ? It could either mean (depending on your book's notations) :

  • $\exists k\in\mathbb Z, |w|_0 + 5k = |w|_1$
  • The remainder from the Euclidean Division of $|w|_1$ by 5 is $|w|_0$

Let's first resolve the first case. You should accept if and only if 5 divides $|w|_1 - |w|_0$. This can be done with a finite automaton with 5 states, to keep track of $|w|_1 - |w|_0\mod 5$ and only accepting when it is in state 0 (I'll let you find the transitions).

In the second case, you need to also ensure that the value of $|w|_0$ never goes beyond 4. That can be done by copying the same finite automaton as above 4 times, fixing the transitions accordingly (I would recommend to try doing that) and adding a "trash state" to go to if you have read more than four 0.

So we have deterministic finite state automata for both those languages. Finite state automata are just specific cases of PDA where you never use the stack. So there you have a DPDA for each of those languages.


Another way to do this, which is probably what the author was looking for, is to try to build a grammar. Hint : such a grammar has 5 non-terminal symbols, 2 terminals symbols, and 11 rules (this is for the first case). Those two constructions are equivalent though.

$\endgroup$
0
$\begingroup$

Your language is regular (it is accepted by a DFA having five states). Every regular language is deterministic context-free. Indeed, a DFA is a PDA which never looks at the stack, and always has exactly one move that it can execute. In other words, the PDA is deterministic, and so the language is deterministic context-free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.