Fdtxjr

Accepted by European university, rejected by all American ones I applied to? Possible reasons?

Was credit for the black hole image misappropriated?

Loose spokes after only a few rides

Drawing arrows from one table cell reference to another

Using dividends to reduce short term capital gains?

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

Does Parliament need to approve the new Brexit delay to 31 October 2019?

Circular reasoning in L'Hopital's rule

Python - Fishing Simulator

Sort list of array linked objects by keys and values

Mortgage adviser recommends a longer term than necessary combined with overpayments

Is there a writing software that you can sort scenes like slides in PowerPoint?

Why don't hard Brexiteers insist on a hard border to prevent illegal immigration after Brexit?

Does Parliament hold absolute power in the UK?

For what reasons would an animal species NOT cross a *horizontal* land bridge?

What happens to a Warlock's expended Spell Slots when they gain a Level?

Presidential Pardon

Why doesn't a hydraulic lever violate conservation of energy?

Why can't wing-mounted spoilers be used to steepen approaches?

Keeping a retro style to sci-fi spaceships?

Deal with toxic manager when you can't quit

Working through the single responsibility principle (SRP) in Python when calls are expensive

My body leaves; my core can stay

What was the last x86 CPU that did not have the x87 floating-point unit built in?

How to Determine which language is guaranteed to be a deterministic Context-Free Language

0

$begingroup$

I'm struggling with figuring out which one of these languages is guaranteed to be a DCFL, i have two languages to choose from and the word guaranteed is throwing me off. Here are the two languages:

Let f1(L) = w : wa ∈ L for some a ∈ Σ

f2(L) = w : aw ∈ L for some a ∈ Σ.

Now my my thoughts are that f2 is guaranteed to be Deterministic because it starts with a state directly "a". Therefore right away it has a decided state, any thoughts?

context-free-grammar

share|cite|improve this question

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  What information are you given about $L$?
  $endgroup$
  – Brian M. Scott
  Nov 12 '14 at 17:21
  

  
  
  
  

add a comment | 

0

$begingroup$

I'm struggling with figuring out which one of these languages is guaranteed to be a DCFL, i have two languages to choose from and the word guaranteed is throwing me off. Here are the two languages:

Let f1(L) = w : wa ∈ L for some a ∈ Σ

f2(L) = w : aw ∈ L for some a ∈ Σ.

Now my my thoughts are that f2 is guaranteed to be Deterministic because it starts with a state directly "a". Therefore right away it has a decided state, any thoughts?

context-free-grammar

share|cite|improve this question

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  What information are you given about $L$?
  $endgroup$
  – Brian M. Scott
  Nov 12 '14 at 17:21
  

  
  
  
  

add a comment | 

$begingroup$

I'm struggling with figuring out which one of these languages is guaranteed to be a DCFL, i have two languages to choose from and the word guaranteed is throwing me off. Here are the two languages:

Let f1(L) = w : wa ∈ L for some a ∈ Σ

f2(L) = w : aw ∈ L for some a ∈ Σ.

Now my my thoughts are that f2 is guaranteed to be Deterministic because it starts with a state directly "a". Therefore right away it has a decided state, any thoughts?

context-free-grammar

share|cite|improve this question

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

$endgroup$

share|cite|improve this question

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

share|cite|improve this question

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

asked Nov 12 '14 at 2:23

drocktapiffdrocktapiff

306

1 Answer
1

active

oldest

votes

0

$begingroup$

I am assuming that this is a question about closure properties of deterministic context-free languages. So let $L$ be a DCFL.

Now $f1(L)$ is again DCFL, as this class is closed under quotients by regular languages: for regular $R$ also $L/R = w mid wy in L mbox for some yin R $ is DCFL.

On the other hand $f2(L)$ is not necessarily DCFL. The operation basically drops the first letter of a string. This letter can be used to distinguish between two possible computations.

share|cite|improve this answer

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1017865%2fhow-to-determine-which-language-is-guaranteed-to-be-a-deterministic-context-free%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

I am assuming that this is a question about closure properties of deterministic context-free languages. So let $L$ be a DCFL.

Now $f1(L)$ is again DCFL, as this class is closed under quotients by regular languages: for regular $R$ also $L/R = w mid wy in L mbox for some yin R $ is DCFL.

On the other hand $f2(L)$ is not necessarily DCFL. The operation basically drops the first letter of a string. This letter can be used to distinguish between two possible computations.

share|cite|improve this answer

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818

$endgroup$

add a comment | 

0

$begingroup$

I am assuming that this is a question about closure properties of deterministic context-free languages. So let $L$ be a DCFL.

Now $f1(L)$ is again DCFL, as this class is closed under quotients by regular languages: for regular $R$ also $L/R = w mid wy in L mbox for some yin R $ is DCFL.

On the other hand $f2(L)$ is not necessarily DCFL. The operation basically drops the first letter of a string. This letter can be used to distinguish between two possible computations.

share|cite|improve this answer

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818

$endgroup$

add a comment | 

$begingroup$

I am assuming that this is a question about closure properties of deterministic context-free languages. So let $L$ be a DCFL.

Now $f1(L)$ is again DCFL, as this class is closed under quotients by regular languages: for regular $R$ also $L/R = w mid wy in L mbox for some yin R $ is DCFL.

On the other hand $f2(L)$ is not necessarily DCFL. The operation basically drops the first letter of a string. This letter can be used to distinguish between two possible computations.

share|cite|improve this answer

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818

$endgroup$

share|cite|improve this answer

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818

answered Nov 15 '14 at 13:43

Hendrik JanHendrik Jan

1,733818