1
$\begingroup$

Could you please help me understand the following Language

$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ what does $a_i = a_{i+1}$ mean? Could you please give me an example of word in $L$?

$\endgroup$
3
  • $\begingroup$ It means exercise 3 b, I should have removed it $\endgroup$ – Michael Maier Mar 7 at 15:25
  • $\begingroup$ I should have removed it Don't muse, do: edit your question. $\endgroup$ – greybeard Mar 7 at 17:06
  • $\begingroup$ (Dubious: $0000$, useful: $0010$, not $0101$: argue why.) $\endgroup$ – greybeard Mar 7 at 17:09
1
$\begingroup$

The expression "$a_i = a_{i+1}$" means "$a_i$ and $a_{i+1}$ are equal".

Presumably $a_i$ is a symbol, that is, $a_i \in \{0,1\}$. Therefore the condition states that $a$ contains at least four symbols, and there are two adjacent symbols which are equal, that is $a$ contains either $00$ or $11$ as a substring. Stated differently, $a$ contains at least four symbols and it doesn't consist of alternating zeroes and ones (i.e. you are not allowing 0101, 01010, ... or 1010, 10101, ...).

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, if I understand it correctly, is for example 010110 a valid word? $\endgroup$ – Michael Maier Mar 7 at 15:34
  • $\begingroup$ Yes, that's a word in the language. $\endgroup$ – Yuval Filmus Mar 7 at 15:36
1
$\begingroup$

Let's break it down

$\{\; a \mid a ∈ \{0, 1\}^∗$ $\quad$ a language of words over the alphabet $\{0,1\}$

$|a| = k ≥ 4$ $\quad$ with length $k$ at least $4$

$a = a_1a_2...a_{k−1}a_k$ $\quad$ lets call the symbols of $a$ with indices $a_1$ to $a_k$ $\quad$

(this is a little implicit here, but OK)

$\exists i \in N$, $1 ≤ i < k$ $\quad$ there exists a natural number $i$, a position in the string $a$,

$a_i = a_{i+1} \; \}$ $\quad$ such that the two consecutive letters $a_i$ and $a_{i+1}$ are equal.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, could you please give an example of such a word? $\endgroup$ – Michael Maier Mar 7 at 15:27
  • $\begingroup$ Please have a look at the answer by @Yuval. He is quite clear in that part, so I do not feel I need to repeat it. (By accident we answered within 8 seconds or so.) $\endgroup$ – Hendrik Jan Mar 7 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.