0
$\begingroup$

Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0} I’m trying to design a PDA. My aproach is:

-for every 2 ‘a’ push an ‘a’

-for every 4 ‘c’ push a ‘c’

-then pop them to solve the 2nd half of the language

This is the first part to count 2 ‘a’, but the ‘c’part is not very clear:enter image description here

Any hints or solutions for the problem: ‘’for every 4 ‘c’ push a ‘c’ on the stack‘’

Thanks!

$\endgroup$
0
$\begingroup$

Use states to record how many 'c' you have seen (0 to 3), use transitions that don't change the stack to move among them when reading 'c'; on a 'c' in a state recording 3 'c', push a 'c' and go back to 0 'c' seen. Can mix/combine freely with e.g. counting the 'a' or 'b'.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You can recognise the language $L = \{c^{4n}|n\geq 0\}$ with a normal DFA. Use this automata as a base and just use one designated state, that pushes a C onto your stack, for which I would choose the first one. For every transition one c is consumed from the word.

$\{(q_1, c, S, CS, q_2) , (q_2, c, S, S, q_3), (q_3, c, S,S,q_4), (q_4, c, S,S,q_1), (q_1, d, C, \varepsilon, q_d)\} \subset \Delta $ with $S \in \Gamma$

| cite | improve this answer | |
$\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.