patternModerate
Is {a^n (a+b)^n | n>0} a Deterministic CFL?
Viewed 0 times
cfldeterministicstackoverflow
Problem
$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?
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?
Solution
You needn't determine the end of "first part".
Note $L$ is exactly the set of strings satisfying the following three constraints:
-
Its length is even.
-
It only contains $a$ and $b$.
-
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.
Note $L$ is exactly the set of strings satisfying the following three constraints:
-
Its length is even.
-
It only contains $a$ and $b$.
-
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.
Context
StackExchange Computer Science Q#89730, answer score: 11
Revisions (0)
No revisions yet.