# 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

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

$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

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

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

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

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 ... 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 ... 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 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 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 0s followed by any number of 1s. This ... 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) ... 4 Take a state machine for M. Given a state \alpha in that machine, we can say that \alpha is L-complete if, for some string y\in L, starting at \alpha, yields a successful match. Now, create a new machine that uses the same state machine as M, but that register a "match" only at the L-complete nodes. You don't really need to know how to ... 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 On the left-hand side you have$$\begin{align} & S^0 \\ \cup & S^0 \cup S^1 \\ \cup & S^0 \cup S^1 \cup S^2 \\ & \qquad \vdots \\ \cup & S^0 \cup S^1 \cup \cdots \cup S^n \\ & \qquad \vdots \end{align}$$On the right-hand side you have$$S^0 \cup S^1 \cup S^2 \cup \cdots S^n \cup \cdots$$Why are these equal? Hint: What is A \cup A ... 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 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 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 The pumping lemma is your friend as it states that if L were regular, there'd be a length n such that all w\in L with |w|>n can be split into w=xyz with y\ne\epsilon such that xy^kz\in L for all k\in\mathbb N_0. We do not know n, but consider one such word w and let a,b,c be the numbers represented by the binary strings x,y,z and ... 4 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 ... 4 That's not quite right. Think of the pumping lemma as a game: Mr. Pumping Lemma gives you a constant n. You choose a word w in the language of length at least n. Mr. Pumping Lemma gives you x, y, and z with xyz=w, |xy|≤n, and y not empty. Now you pick r. Mr. Pumping Lemma asserts that xy^rz is also in the language. If he's wrong, you ... 4 Your intuition is correct. To prove it correct, the most straightforward aproach is to show the two inclusions A\subseteq A^* and A^*\subseteq A. The first one of these is trivially true for every A. For the second one, suppose w is a member of A^*; our task is then to show that w\in A. By definition of A^*, w is the concatenation of zero or ... 3 If a language contains the strings v_1, v_2, v_3,\dots, v_n, one possible expression is$$ v_1\cup v_2\cup v_3 \cup ...\cup v_n=\bigcup_{i=1}^n v_i.  $\cup$ is also commonly written $|$, especially on computers. Since there is a regular expression for the language, the language is regular.

3

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 ...

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