# Tag Info

34

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

10

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

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

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

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

$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

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

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 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 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 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 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 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 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 ... 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 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 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 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 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 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 ... 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 ... 3 I assume that you meant "... such that every deterministic automaton that accepts the language L(M)^R...", otherwise the statement isn't true. It's known that there are some languages accepted by an n+1-state NFA for which the smallest equivalent DFA requires 2^n states. For example, Hopcroft/Motwani/Ullman show this in their Introduction to Automata ... 3 For any fixed value of n, the language$$ L_{n}=\{w:|w|_a=2^n+273\} $$is certainly regular, and the regular expression you described will recognize it. But the question here is whether$$ L=\bigcup_{n\in\mathbb{N}}L_n = \{w:|w|_a=2^n+273 \text{ for some } n\in\mathbb{N}\}  is regular. It's not; and the easiest way to prove it is to use the so-called ...

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

3

$L_1=\{ n^p\quad |\quad \text{p=prime number} \}$ is not regular language ,can easily be proved by pumping lemma. Let $k$ be the pumping lemma constant. and the string $\alpha \beta \gamma$ as $\epsilon$ , $a^p$ and $\epsilon$ respectively such that $\alpha \beta \gamma \in L_1$ and $|\beta|\geq k$. So ,if we decompose $\beta$ into \$\beta ...

3

In general, for reductions to be a useful reasoning concept, we need to require that the reduction function is easy enough to compute that it can be done within the same resource constraints as the complexity class we're ultimately interested in. Because the class of regular languages correspond to the very weak computational model of finite-state machines, ...

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