8
$\begingroup$

$L = \{ a^n (a+b)^n | n>0\}$

A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using a DPDA? Like after reading the first part ($a^n$) how can we be sure that it's the end of the first part or not considering the second part can also start with $a? $

Is this Deterministic?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

You needn't determine the end of "first part".

Note $L$ is exactly the set of strings satisfying the following three constraints:

  1. Its length is even.

  2. It only contains $a$ and $b$.

  3. The first $b$ appears in its latter half.

Constraints 1 and 2 are easy to check. To check constraint 3, the DPDA can push a symbol to its stack each time it reads a character until the first $b$ appears (excluding), and then pop a symbol each time it reads a character. Constraint 3 is satisfied if and only if the initial stack symbol is never read during the popping process.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks for the answer, So in the DPDA we should push a ball every time we read a character until we reach the first b, but in this way the string aaab will not get accepted tho? because when we reach the first b we have 3 ball and we gonna only pop 1 ball and the stack is not empty, assuming we'll accept without the empty stack, then when will we go to the final state? if the stack is not empty and no more input is available? $\endgroup$
    – John P
    Mar 24, 2018 at 12:15
  • $\begingroup$ @JohnP Sorry that I didn't read the formal description of a PDA so the answer before editing may be confusing. Now I have modified the answer to make it compatible with the formal definition in Wikipedia. For your question, when the automaton reads the initial stack symbol, it transforms to a special state representing "reject" (then loop for the rest inputs) and all other states are accepting states (except the start state, since $n>0$). $\endgroup$
    – xskxzr
    Jul 11, 2018 at 5:29
  • $\begingroup$ I am not sure how all the constraints can be checked without losing determinism. Can you hint or tell transition functions? $\endgroup$
    – Mr. Sigma.
    Jul 11, 2018 at 9:52
  • $\begingroup$ @Rohith. First, it is in state A and when the input is $a$, push a symbol. When the input is $b$, turn to state B and pop a symbol. In state B, every time it sees $a$ or $b$, pop a symbol. $\endgroup$
    – xskxzr
    Jul 11, 2018 at 10:55
  • $\begingroup$ When to start popping if $w=a^{2n}$ ? $\endgroup$
    – Mr. Sigma.
    Jul 11, 2018 at 12:31
4
$\begingroup$

In case it's clearer, here's a CFG corresponding to xskxzr's DPDA:

$$\begin{align} S&\to \epsilon \\ S&\to B \\ S&\to a a S \\ B&\to a b \\ B&\to a B a \\ B&\to a B b \\ \end{align} $$

The slightly simpler CFG below is ambiguous for inputs consisting only of an even number of $a$s, but it still works with the LALR(1) algorithm using the "standard" conflict resolution algorithm: "in case of ambiguity, shift":

$$\begin{align} S&\to B \\ S&\to a a S \\ B&\to \epsilon \\ B&\to a B a \\ B&\to a B b \\ \end{align} $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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