Skip to main content
added 4 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| >= m$$|w| \geq m$ is fulfilled. I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| <= m$$|xy| \leq m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?

as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| >= m$ is fulfilled. I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| <= m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?

as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| \geq m$ is fulfilled. I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| \leq m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?

Source Link

Proof that a language is not regular

as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| >= m$ is fulfilled. I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| <= m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?