Tag Info

Hot answers tagged

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 $0$s followed by the same number of $1$s. 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