Binary strings such that the sum of 0's is not equal to twice the sum of 1'sWhat is complement of Context-free languages?Are context-free languages in $a^*b^*$ closed under complement?Is the language $L = a^ib^j mid i nmid j $ context free?Prove that context free languages are not closed under swapping prefixes and suffixesPushdown automaton for complement of … Examples of context-free languages with a non-context-free complementsIs there $L$ such that $L$ and $bar L$ are context free, but $L$ is not deterministic context free?Is the Complement of the Language $L=wxw^r$ Context free?Can the complement of a context-free language be regular?How can the union of two 'context-free but not regular' languages be regular?
Output a Super Mario Image
Why don't airports use arresting gears to recover energy from landing passenger planes?
How To Make Earth's Oceans as Brackish as Lyr's
Make 1998 using the least possible digits 8
Seven Places at Once - Another Google Earth Challenge?
Are there any “Third Order” acronyms used in space exploration?
Insight into cavity resonators
Why is the UK still pressing on with Brexit?
Wrong Schengen Visa exit stamp on my passport, who can I complain to?
What is the meaning of 「ぞんぞん」?
How to give my students a straightedge instead of a ruler
Importance of the current postdoc advisor's letter in TT job search
What is the meaning of "order" in this quote?
Would it be unbalanced to increase a druid's number of uses of Wild Shape based on level?
Why are some files not movable on Windows 10?
Work done by spring force
Prove that a convergent real sequence always has a smallest or a largest term
Why is the year in this ISO timestamp not 2019?
If I want an interpretable model, are there methods other than Linear Regression?
How to control the output voltage of a solid state relay
Why is belonging not transitive?
Is "you will become a subject matter expert" code for "you'll be working on your own 100% of the time"?
In what sequence should an advanced civilization teach technology to medieval society to maximize rate of adoption?
Is my sink P-trap too low?
Binary strings such that the sum of 0's is not equal to twice the sum of 1's
What is complement of Context-free languages?Are context-free languages in $a^*b^*$ closed under complement?Is the language $L = a^ib^j mid i nmid j $ context free?Prove that context free languages are not closed under swapping prefixes and suffixesPushdown automaton for complement of … Examples of context-free languages with a non-context-free complementsIs there $L$ such that $L$ and $bar L$ are context free, but $L$ is not deterministic context free?Is the Complement of the Language $L=wxw^r$ Context free?Can the complement of a context-free language be regular?How can the union of two 'context-free but not regular' languages be regular?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Construct a context-free language for $L=win 0,1^* mid n_0(w)not= 2n_1(w)$. Here $n_b(w)$ is the number of $b$'s in $w$.
I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.
context-free
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
$endgroup$
add a comment
|
$begingroup$
Construct a context-free language for $L=win 0,1^* mid n_0(w)not= 2n_1(w)$. Here $n_b(w)$ is the number of $b$'s in $w$.
I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.
context-free
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
$endgroup$
add a comment
|
$begingroup$
Construct a context-free language for $L=win 0,1^* mid n_0(w)not= 2n_1(w)$. Here $n_b(w)$ is the number of $b$'s in $w$.
I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.
context-free
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
$endgroup$
Construct a context-free language for $L=win 0,1^* mid n_0(w)not= 2n_1(w)$. Here $n_b(w)$ is the number of $b$'s in $w$.
I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.
context-free
context-free
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
edited Apr 15 at 8:10
dkaeae
4,5251 gold badge11 silver badges29 bronze badges
4,5251 gold badge11 silver badges29 bronze badges
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
asked Apr 15 at 7:19
My_LuluMy_Lulu
61 bronze badge
61 bronze badge
add a comment
|
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
$endgroup$
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106973%2fbinary-strings-such-that-the-sum-of-0s-is-not-equal-to-twice-the-sum-of-1s%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
$endgroup$
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
add a comment
|
$begingroup$
Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
$endgroup$
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
add a comment
|
$begingroup$
Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
$endgroup$
Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
answered Apr 15 at 7:35
Hendrik JanHendrik Jan
22.3k29 silver badges76 bronze badges
22.3k29 silver badges76 bronze badges
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
add a comment
|
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)ge 2n_1(w)$. Then we can have $Arightarrow S0B$, $Brightarrow S|A$.
$endgroup$
– My_Lulu
Apr 15 at 9:36
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
$begingroup$
Well, I just make it too complex. Thanks!
$endgroup$
– My_Lulu
Apr 15 at 10:44
add a comment
|
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106973%2fbinary-strings-such-that-the-sum-of-0s-is-not-equal-to-twice-the-sum-of-1s%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
