Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Since you want to master the process, I'll point out a few things before showing a proof.</p> <ol> <li><p>The first thing to notice is that the <code>+</code> and the <code>=</code> may only appear once each. So when you write your string <code>w</code> as <code>w = abc</code>, the pumped portion, <code>b</code>, cannot contain <code>+</code> or <code>=</code> otherwise you'd reach a trivial contradiction (I'm not using the more standard <code>w = xyz</code> notation to avoid confusion with <code>L</code>'s definition). </p></li> <li><p>Another thing to notice is that normally, you'd pick a specific string <code>w</code> to pump. In this case, it <em>could</em> be easier to pick a class of strings that share a certain property. The pumping lemma only requires you to reach a contratiction using one string, but there's no reason you can't reach a contradiction with multiple strings.</p></li> </ol> <p>Proof (in a spoiler): </p> <blockquote class="spoiler"> <p> So let <code>w</code> be any string in <code>L</code> such that <code>|w| ≥ P</code> and <code>x, y, z</code> do not contain leading <code>0</code>'s. By the pumping lemma we can write <code>w</code> as <code>w = abc</code> By pumping lemma, we know <code>b</code> is not empty. Since <code>b</code> cannot contain <code>+</code> or <code>=</code>, it is fully contained in either <code>x, y,</code> or <code>z</code>. Pumping <code>w</code> with any i &ne; 1 results in the binary equation no longer holding since exactly one of <code>x, y, z</code> would be a different number (this is why we needed the no leading <code>0</code>'s bit).</p> </blockquote>
    singulars
    1. This table or related slice is empty.
    1. POCan someone help me with this proof using the pumping lemma?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDPenner1
    1. USDPenner1
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POCan someone help me with this proof using the pumping lemma?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you very much for the help. I understand now. Since the equation must not change it means that our assumption about the language being regular is not correct and thus it has to be non regular. I get it now, thank you! Well done with the spoiler :)
      singulars
      1. PO
      1. USn00b1990
    2. COAlthough I am very curious. How can you tell when picking a class of strings is easier then one single string? And what would happen if b did contain a `+ or =` ? Wouldn't that be enough to reach a contradiction and thus a proof?
      singulars
      1. PO
      1. USn00b1990
    3. COAs for choosing a class of strings, it was marginally easier for me, because my thought process was: "Now I need to pump b such that the number changes." And `b`'s which always satisfy that are the ones without leading zeroes. So now that I knew that, I really didn't need to find a specific string, that would just be an extra step. However, like @Patrick87 did, picking a specific string is still completely valid, and depending on your thought process, could be easier.
      singulars
      1. PO
      1. USDPenner1
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload