Linked Questions

146 votes
3 answers
20k views

How can it be decidable whether $\pi$ has some sequence of digits?

We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ ...
Raphael's user avatar
  • 72.6k
17 votes
5 answers
4k views

Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
Ben Elgar's user avatar
  • 271
16 votes
4 answers
5k views

Algorithms computing if a number is a multiple of 3

When doing mental calculus one can do: Given an integer k, sum all the digits (in base 10), and if the result is a multiple of 3, then k is a multiple of 3. Do you know of any algorithm working ...
Stephane Rolland's user avatar
7 votes
2 answers
533 views

Is this language regular or not?

$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$. If it is regular, I haven't found its regular expression or any closure property to prove it. If not, it seems ...
goldfrapp04's user avatar
7 votes
2 answers
2k views

Automaton for telling whether a binary number is a multiple of 3

I am designing an automaton which determines whether a binary number is divisible by 3: $$ \{x \in \{0, 1\}^* \mid \text{$x$ represents a multiple of three in binary} \} $$ 0 1 0F 0 1 1 2 0 2 1 2 ...
user avatar
5 votes
3 answers
15k views

Regular expression for strings that begin with 0 and contain an equal number of 01 and 10 substrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
Lurr's user avatar
  • 147
4 votes
2 answers
462 views

Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?

I need to prove or disprove if these two languages are same. So I assume that these lanaguages are same because I think that every word from $\{a,b\}^*$ could be concatenated from two words $x$ and $y$...
Johny's user avatar
  • 155
4 votes
1 answer
421 views

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), ...
remo's user avatar
  • 141
1 vote
1 answer
571 views

Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

I'm doing a problem where I need to find the equivalence classes of the language below: Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x ...
James Swanson's user avatar
0 votes
1 answer
163 views

DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ } [closed]

I need to find a DFA for this language: L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }
lluc22's user avatar
  • 17
0 votes
1 answer
165 views

How to check $L$ is regular or not [duplicate]

If $L=\{w \in \Sigma^*\mid w=uv,\text{ number of occurnce a's in $u$ equal to number of occurrence b's in $v$}\}.$ I think $L=\Sigma^*$ because for any string in $\Sigma^*$, we can split it to $uv$ ...
user avatar
0 votes
0 answers
561 views

Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states

Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
cinch's user avatar
  • 235
-2 votes
1 answer
114 views

Finite strings and relationships between words [closed]

I have a finite alphabet Σ and Σ* refers to the set of all finite strings over Σ. 1) Given x, y ∈ Σ* we say that x is a prefix of y if ∃z ∈ Σ* y = xz. If x is a prefix of y and y is a prefix of x ...
user40164's user avatar