Skip to main content
Notice removed Reward existing answer by Hendrik Jan
Bounty Ended with Gilles 'SO- stop being evil''s answer chosen by Hendrik Jan
Notice added Reward existing answer by Hendrik Jan
Bounty Started worth 100 reputation by Hendrik Jan
Tweeted twitter.com/#!/StackCompSci/status/481164283079061504
Post Reopened by András Salamon, Gilles 'SO- stop being evil'
added information from comment
Source Link

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language. My guess is we can construct the language with an NPDA where after reading some $a$ and $b$ and pushing $A$ for each $a$ into the stack, makes a guess to jump to a new state and consumes the pushed $A$ with each $b$.

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language.

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language. My guess is we can construct the language with an NPDA where after reading some $a$ and $b$ and pushing $A$ for each $a$ into the stack, makes a guess to jump to a new state and consumes the pushed $A$ with each $b$.

title, formatting, language; removes superfluous "no homework" assertions
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

If Is the language isof words with as many a's in the first as b's in the second part context free-free?

I have a simple question. A student in computer science asked me the question. This is not her homework (This is the starting semester point in our country!). IfIs $W_1W_2 | W_1,W_2 \in (a+b)^* , N_a(W_1)=N_b(W_2)$ is$L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? If NPDA canCan we construct an NPDA for the language? 

There is a book here that claimed thisclaims $L$ is not CF (without any description :( elaboration), but I think we can construct a NPDA to buildthat accepts the language.

If the language is context free

I have a simple question. A student in computer science asked me the question. This is not her homework (This is the starting semester point in our country!). If $W_1W_2 | W_1,W_2 \in (a+b)^* , N_a(W_1)=N_b(W_2)$ is context free? If NPDA can construct the language? There is a book here that claimed this is not CF (without any description :( ), but I think we can construct a NPDA to build the language.

Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? 

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language.

added 275 characters in body
Source Link
remo
  • 141
  • 3

I have a simple question. IfA student in computer science asked me the question. This is not her homework (This is the starting semester point in our country!). If $W_1W_2 | W_1,W_2 \in (a+b)^* , N_a(W_1)=N_b(W_2)$ is context free? If NPDA can construct the language? There is a book here that claimed this is not CF (without any description :( ), but I think we can construct a NPDA to build the language.

I have a simple question. If $W_1W_2 | W_1,W_2 \in (a+b)^* , N_a(W_1)=N_b(W_2)$ is context free? If NPDA can construct the language?

I have a simple question. A student in computer science asked me the question. This is not her homework (This is the starting semester point in our country!). If $W_1W_2 | W_1,W_2 \in (a+b)^* , N_a(W_1)=N_b(W_2)$ is context free? If NPDA can construct the language? There is a book here that claimed this is not CF (without any description :( ), but I think we can construct a NPDA to build the language.

Post Closed as "Needs details or clarity" by Raphael
Source Link
remo
  • 141
  • 3
Loading