<p>Let $A=\{a^nb^nc^m\mid m,n\ge0\}$, $B=\{a^nb^mc^m\mid m,n\ge 0\}$, and $L=dA \cup B$. Then the homomorphism $h:\{a,b,c,d\}\to\{a,b,c\}$ defined by $h(a)=a$, $h(b)=b$, $h(c)=c$, and $h(d)=\epsilon$ gives $h(L)= A \cup B$ which is not a DCFL.</p>

CC BY-SA 3.0
2012-11-23T22:43:25.797Z
2012-12-30T18:41:30.850Z
2012-12-30T18:41:30.850Z
M.K. Dadsetani
<p>It's easy:</p>

<p>Take this Deterministic-CFL L = {$a^{l}b^{m}c^{n}\,|\, m=n$} and take this homomorphism-function:<br/> 
h(a)=b, <br/>
h(b)=b, <br/>
h(c)=c. <br/>
Then this homomorphism on L looks like this $$h(L)=\{{b^{l}b^{m}c^{n}\,|\, m=n}\}$$</p>

<p>Now there is no Deterministc-PDA for this anymore, because the PDA would have to guess the end of the first "package" of b's ($b^{l}$).</p>

CC BY-SA 3.0
2012-11-24T00:29:13.673Z
Your language $h(L)$ is deterministic: it is better expressed as $\{b^m c^n\mid m\geq n\}$.  And do please post on cs instead of cstheory for basic questions.
Sylvain
CC BY-SA 3.0
2012-06-24T10:01:36.190Z
2012-06-24T10:01:36.190Z
kiltek
<p>I tried to research the following question with no results: Can you find one example where the following holds true:</p>

<p>Let  L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx be a Homomorphism.
Then the Homomorphism on that language L h(L) ist NOT a deterministic-CFG anymore.</p>

CC BY-SA 3.0
2012-06-24T01:07:21.337Z
I do not know the answer, but how do you know that there is an example?  Maybe I am misunderstanding the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-24T09:13:42.100Z
I made up an example myself 10 minutes after my post. I am going to post it soon.
kiltek
CC BY-SA 3.0
2012-06-24T10:27:22.833Z
@kiltek Accept your answer then also.
Joshua Herman
CC BY-SA 3.0
2012-06-24T10:36:07.130Z
possbile tomorrow
kiltek
CC BY-SA 3.0
2012-06-25T02:04:27.653Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
CC BY-SA 3.0
2012-06-25T06:43:23.497Z
Kaveh thanks for your down vote. I hope you can GET IT UP again.
kiltek
CC BY-SA 3.0
2012-06-25T15:44:18.993Z
Your solution is incorrect. Please post the question to [cs.stackexchange](http://cs.stackexchange.com).
sdcvvc
CC BY-SA 3.0
2012-06-26T18:05:38.487Z
Why is the solution incorrect. explain.
kiltek
CC BY-SA 3.0
2012-06-27T12:43:56.760Z
You have not answered my question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-28T12:48:53.563Z
@Tsuyoshi Ito: What part did you not understand? What a deterministic-CFG is? What determinism in general is? Or something else?
kiltek
CC BY-SA 3.0
2012-06-28T13:01:12.423Z
In [revision 1](http://cstheory.stackexchange.com/revisions/11792/1), you claimed that a homomorhpic image of a DCFL is not necessarily DCFL.  At the same time, you asked for an example.  This means that you knew there is an example, yet you did not know an example.  I was wondering how that could happen.  But honestly, I do not want to talk to you anymore after seeing your rude replies to Kaveh and sdcvvc.  This is my last comment in this thread.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-28T13:43:06.317Z
ok, i grant you that, but one thing remains: What is wrong with my example. I think it is a 100% correct.
kiltek
CC BY-SA 3.0
2012-12-06T07:56:17.827Z
Please consider reposting the question on [cs.se] which has a broader scope. ps: I would have migrated the question there however the system does not allow it (it is too old for migration).
Kaveh
<reference-request><fl.formal-languages><context-free-languages>
Deterministic CFL closure Property Homomorphism
kiltek
# Deterministic CFL closure Property Homomorphism

(Asked by: username_0 on 2012-06-23)

I tried to research the following question with no results: Can you find one example where the following holds true:

Let L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx be a Homomorphism.
Then the Homomorphism on that language L h(L) ist NOT a deterministic-CFG anymore.

**Tags:** reference-request, fl.formal-languages, context-free-languages

> **Comments:**
> **username_1**: I do not know the answer, but how do you know that there is an example?  Maybe I am misunderstanding the question.  
> **username_0**: I made up an example myself 10 minutes after my post. I am going to post it soon.  
> **username_2**: @username_0 Accept your answer then also.  
> **username_0**: possbile tomorrow  
> **username_3**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  
> **username_0**: username_3 thanks for your down vote. I hope you can GET IT UP again.  
> **username_4**: Your solution is incorrect. Please post the question to [cs.stackexchange](http://cs.stackexchange.com).  
> **username_0**: Why is the solution incorrect. explain.  
> **username_1**: You have not answered my question.  
> **username_0**: @username_1: What part did you not understand? What a deterministic-CFG is? What determinism in general is? Or something else?  
> **username_1**: In [revision 1](http://cstheory.stackexchange.com/revisions/11792/1), you claimed that a homomorhpic image of a DCFL is not necessarily DCFL.  At the same time, you asked for an example.  This means that you knew there is an example, yet you did not know an example.  I was wondering how that could happen.  But honestly, I do not want to talk to you anymore after seeing your rude replies to username_3 and username_4.  This is my last comment in this thread.  
> **username_0**: ok, i grant you that, but one thing remains: What is wrong with my example. I think it is a 100% correct.  
> **username_3**: Please consider reposting the question on [cs.se] which has a broader scope. ps: I would have migrated the question there however the system does not allow it (it is too old for migration).  

---

## 2 answers

### Answer by username_5 on 2012-11-23. Score: 1

Let $A=\{a^nb^nc^m\mid m,n\ge0\}$, $B=\{a^nb^mc^m\mid m,n\ge 0\}$, and $L=dA \cup B$. Then the homomorphism $h:\{a,b,c,d\}\to\{a,b,c\}$ defined by $h(a)=a$, $h(b)=b$, $h(c)=c$, and $h(d)=\epsilon$ gives $h(L)= A \cup B$ which is not a DCFL.


---

### Answer by username_0 on 2012-06-24. Score: 0

It's easy:

Take this Deterministic-CFL L = {$a^{l}b^{m}c^{n}\,|\, m=n$} and take this homomorphism-function:  
h(a)=b,   
h(b)=b,   
h(c)=c.   
Then this homomorphism on L looks like this $$h(L)=\{{b^{l}b^{m}c^{n}\,|\, m=n}\}$$

Now there is no Deterministc-PDA for this anymore, because the PDA would have to guess the end of the first "package" of b's ($b^{l}$).

> **Comments:**
> **username_6**: Your language $h(L)$ is deterministic: it is better expressed as $\{b^m c^n\mid m\geq n\}$.  And do please post on cs instead of cstheory for basic questions.  

---

