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$ Mar 7 at 15:25
  • 1
    $\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$ Mar 7 at 15:34
  • $\begingroup$ Yes, that's a word in the language. $\endgroup$ 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$ 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$ 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.