# Tag Info

35

Well, a valid C++ program (or really any C++ program) will simply be a finite sequence composed of a finite collection of characters and a few other things (indentation, spaces, etc.). It is a general result that the set of all finite sequences of entries from a finite alphabet will be countably infinite. To show that there are countably infinitely many ...

23

Countably infinite doesn't mean regular. The C++ grammar isn't regular. In fact, it isn't even context free. Yet, the set of all valid C++ programs is countably infinite. To see why, first notice that it's infinite. No matter what $n \in \mathbb{N}$ you pick, you can always write a C++ program that is longer than $n$. Next, let $S_n$ be the set of all C++ ...

12

A C++ program is a finite sequence of characters in a specified finite alphabet. The set of all finite sequences of characters in that alphabet is countably infinite. The set of all valid C++ programs is a subset of the set of all finite sequences of characters in that alphabet. An infinite subset of a countably infinite set is countably infinite. (It's ...

11

The reason to treat a programming language as context-free is that the context-free grammar tells how to parse the language. If you considered just the subset of C consisting of programs of length no more than $2^{32}$ that would be regular, but the regular expression would likely consist of millions of individual cases, and wouldn't be helpful for parsing ...

6

Are you saying that you know how to prove if a language is regular, and you know how to prove that a language is irregular, but you don't know how to decide which strategy to try? Then try both! Try one strategy for awhile, then try the other. Guessing is a time-honored mathematical strategy. As far as intuition goes, the informal test for regularity is "if ...

6

$(aa+\lambda)(aaaaa)^*$ should do.

6

Think of the Pumping Lemma as a game in which you're trying to prove that a language isn't regular, while someone else is "defending" the regularity of this language. Here is how to play the game: The defender specifies the pumping length $n$. Think of it as the number of states in the automata that recognizes the language. You give the defender a word $w$ ...

5

Hint: $L = L_1 \cap L_2$ where $L_1 = \{a^*b^*c^*\}$ and $L_2 = \{w \in \Sigma^* : |w|\text{ is even}\}$.

5

You can do that by building a FSA with 6 states: $a$ is even $a$ is odd $a+b$ is even $a+b$ is odd $a+b+c$ is even $a+b+c$ is odd

5

There is a systematic way for creating automatons for intersection of languages. Let $A$ and $B$ be the input automatons. The states of new automaton will be all pairs of states of $A$ and $B$, that is $S_{A\cap B} = S_A \times S_B$, the initial state will be $i_{A \cap B} = \langle i_A, i_B \rangle$, where $i_A$ and $i_B$ are the initial states of $A$ and ...

5

The condition that no proper prefix is in $L$ means that the input should be rejected if you encounter an accepting state before the word is completely read. So you could use a FSM for $L$ with the modification that from an accepting state all transitions are redirected to a non-accepting error state. Edit: Of course, one has to assume w.l.o.g. that the FSM ...

5

There is a very natural model of finite-state reduction, namely the most general finite-state transducer -- one input tape, one output tape, non-deterministic, transitions can be labelled with arbitrary regular sets (with empty strings) on both the input and output side. This can be shown equivalent to Henning's single-symbol operations, but allows for much ...

5

The empty language is a regular subset of any language at all. More generally, every finite subset of any language is regular. For example, let $L$ be the language $\{ a^n | n\text{ is prime} \} = \{ aa, aaa, aaaaa, a^7, \ldots\}$. Let $R$ be the subset of $L$ consisting just of $\{ aa, aaaaa, a^{11}, a^{109} \}$. Then $L$ is not regular, but $R$ is.

5

You don’t choose the pumping length: the lemma says that if the language is regular, there is a pumping length, but it doesn’t say what that length is. Thus, when you’re using the pumping lemma to prove that a language $L$ is not regular, you can only assume that there is a pumping length $n$; you can’t assume that it’s related to the definition of the ...

5

$L$ should also work for NFAs. Suppose that $M$ is an NFA with fewer than $2^{200}$ states that accepts every word of $L$. For each $u\in\{0,1\}^{200}$ let $s_u=\langle s_u(0),s_u(1),\dots,s_u(400)\rangle$ be the sequence of states of $M$ along some path by which $M$ accepts $uu$. Then there must be $u,v\in\{0,1\}^{200}$ such that $u\ne v$ and ...

5

Let $\underline \Sigma := \{ \underline a : a \in \Sigma \}$ be a disjoint copy of $\Sigma$, assume $<$ and $>$ are symbols not already present in $\Sigma$ and define a homomorphism $h: \Sigma \cup \underline \Sigma \cup \{<,>\} \to \Sigma$ by \begin{align*} a &\mapsto a,\\ \underline a &\mapsto a,\\ < &\mapsto \varepsilon,\\ > ...

5

Actually, in the sense of the program, you can make a computer as power as the universal Turing Machine. (In fact, the computer you are on probably is.) More precisely, you can write down explicitly a universal Turing Machine in many of the actual computer languages out there. So in a very real-world sense, there are computer program much more power than any ...

5

You can use $${\rm maj}(A,B,C)=(A\cap B)\cup(A\cap C)\cup(B\cap C).$$

5

You can also combine DFAs for $A,B$, and $C$ to make one that accepts $\operatorname{maj}(A,B,C)$. The basic idea is that if the state sets of the original DFAs are $Q_A,Q_B$, and $Q_C$, the state set of the new one will be $Q_A\times Q_B\times Q_C$. For each $\alpha$ in the input alphabet you’ll have a transition $$\langle ... 4 This is not a regular language. The "problem" is you need to count how many 010 and how many 101 strings appear in a word and regular languages don't know how to do this. For a more formal proof start by defining a homomorphism 0 \mapsto 00100 and 1 \mapsto 11011. If your language was regular, then the inverse image of the homomorphism is also ... 4 One easy if tedious approach is to design a finite-state automaton that recognizes L and then apply the algorithm that converts such an automaton to a corresponding regular expression. Going about it directly, I observe that if w\in L, every a in w must be immediately followed by another a or a c or be at the end of the word; otherwise there are ... 4 You could cheat. If L is regular, then its complement (in the regular language given by a^* b^*) is also regular. That complement is \{ a^k b^k \mid k \geq 0 \} and you can show that is non-regular using the pumping lemma. To totally avoid the pumping lemma, you could use the Myhill-Nerode Theorem; I'm paraphrasing the formulation below from ... 4 If A and B are regular languages, so is B\setminus A, so the problem really boils down to showing that if L is an infinite regular language, there is an infinite regular language L'@L. HINT: Let p be the pumping length for L, and let w\in L be any word of length at least p. Decompose w as w=xyz, where |xy|\le p, |y|\ge 1, and ... 4 What I do is the following: If I suspect that it is a regular language (usually by checking whether you need to save some information or whether you have to be able count): First I check whether I can easily come up with a DFA / NFA. If that does not work, I check whether it is the union/intersection/... of languages that are pritty well known to be ... 4 Shouldn't v^i be repetition of v, not a power of the number v? That seems more likely since we are talking about strings. In that case u=12,v=34,w=56 is not correct. The classic divisibility rule says that a number is a multiple of 3 if and only if the sum of the digits is. So as long as the sum of the digits in your string is a multiple of ... 4 Consider the language of all words that start with any number of 0s followed by the same number of 1s. You should be able to prove that this language is not regular using the pumping lemma:$$ L_1 = \left\{0^i 1^i \mid i \ge 0 \right\}  Also, consider the language of all words that start with any number of $0$s followed by any number of $1$s. This ...

4

It's not recursive, because if you can decide if $\langle M,q,x\rangle$ is in your language, then you can decide if the machine $M$ stop on entry $x$, by testing if $\langle M,h,x\rangle$ is in your language ($h$ is the halting state). So you can decide the halting problem. And this problem is uncomputable, so is your language. But it's obviously RE, as you ...

4

No. $\Sigma^\ast$ is regular, but not all $L \subseteq \Sigma^\ast$ are regular.

4

I propose the following: Each natural number is a program (a file is nothing but a very large number). Some of these programs are valid C++ programs. If we show now, that for every valid C++ program n, there exists a program n + m that is a valid C++ program as well, the number of C++ programs is countable infinite. Let n_0 be a classical hello world ...

4

Hint: You have given a perfectly good proof that $L_2$ is regular. To show that $L_1$ is not regular, use the Pumping Lemma. Suppose to the contrary that the language is regular. Since there are arbitrarily large primes, there are integers $a$ and $d\gt 0$ such that all strings of length $a+kd$ are in the language. But the arithmetic sequence $(a+kd)$ ...

Only top voted, non community-wiki answers of a minimum length are eligible