# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

2k views

### Why isn't this a regular language?

I'm stuck as to figuring out why $L_1$={$n^p$ | $p$ = a prime number} is not a regular language but $L_2$={$n^p$ | $p$ = a prime number bounded by some fixed number f} is. I can see that $L_2$ is a ...
818 views

### If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
90 views

### Regular expression 00 or 11 not both

Can anyone help me with this question: I know it before, but I have tried to solve it myself and didnt succeed. what is the regular expression for this language: L=all words that have 00 or 11 but not ...
7k views

### Formally prove that every finite language is regular

I know how to prove this informally, but don't know what the formal proof should look like.
4k views

### Application of Pumping lemma for regular languages

I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular. According to the Pumping lemma for each regular language a word $w = xyz$ exists, that ...
I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every {\tt a} in s is ... 1answer 142 views ### show that language L' is regular (given L regular) Let L be a regular language. Show that L'=\{x \mid\exists_{y,z} xyz\in L \text{ and }|x|=|y|=|z|\} is also regular. Firstly I show my idea. When you accept it I will try to formalize it. Every ... 2answers 143 views ### Is \frac12 L a regular language? Let L be a regular language. Is \frac{1}{2}L := \left\{ w: \exists_u |u|=|w| \wedge wu\in L \right\} regular too? I think the answer is YES. But I don't know how to prove it. I was trying to ... 2answers 2k views ### suffix regular language Can someone give me an idea how to prove this: suffix(L) = {y | xy \in  L for some x \in \Sigma *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ... 1answer 24 views ### Finding the language of a finite automaton Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton A is L(A) = (a ... 4answers 40 views ### Regular expressions: Show that A*B is the solution of X = AX + B I'm currently working on the following problem for my computer theory class. It goes as follows: Let A and B be regular expressions. Show then that A^*B is the solution of X = AX + B ... 2answers 135 views ### Formal Languages - Regular Expression I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ... 8answers 4k views ### Is the set of all valid C++ programs countably infinite? I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ... 1answer 37 views ### Is L_1 context free language? Let L = L_1 \cap L_2 , where L_1 and L_2 are languages as defined below: L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \} L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \} Then L ... 3answers 387 views ### Deciding equivalence of regular languages Given two regular expressions R and S on an alphabet \Sigma it is possible to decide their equivalence as follows: build two finite automata M_R and M_S such that L(R) = L(M_R) and L(S) ... 2answers 3k views ### Are regular languages necessarily deterministic context-free languages? The original problem Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers. a) Is M-N necessarily context-free? ... 1answer 3k views ### Quotient of a regular language According to wikipedia the right quotient of a regular language with ANY other language is regular. I have not been able to find a proof of this fact. All the sources talk about quotient with another ... 1answer 60 views ### Write the regular expression of the language that the DFA accepts. I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ... 1answer 443 views ### Possible solution for Sipser 1.63 Sipser's question 1.63: Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets. Is my solution correct? Since A is infinite and ... 1answer 336 views ### Prove the following language is not regular The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime. I'm assuming the best way to move forward is to use the pumping lemma. I'm ... 1answer 462 views ### A regular expression for the words that don't contain the sequence ab over \{a,b,c\} The following is an exercise in a book I am reading: Let \Sigma=\{a,b,c\}, define L to be the language of all words over \Sigma that do not contain ab as a sub-word. Find a regular ... 0answers 110 views ### Prove that whenever L is a regular language so is HasPrefix(L) For a language L over an alphabet \Sigma, deﬁne the language \operatorname{HasPrefix}(L) as follows:$$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$... 1answer 35 views ### Is C* regular if C is a language with strings of prime length? Let C = \{a^p \ | \ p \ \text{is prime}\} be a language. I was able to show that C is not regular using the pumping lemma. However, I am having some trouble showing that C^* is regular. ... 1answer 37 views ### Regular languages- homomorphism. Let h: \{ a,b,c,d \}^* \rightarrow \{a,b\}^*  be a homomorphism such, that h(a) = aa, h(b) = ab, h(c) = ba, h(d) = b  . Determine: h^{-1}((bab)^*ba^*b). I have trying do it by 4 hours. I don't ... 1answer 64 views ### Non regular language that satisfies pumping lemma Let$$L = \{ ww^rx \mid w,x \in \{a,b \}^+\} $$where \{a,b\}^+ means the set of words over \{a,b \} that has at least length 1, and w^r is the reverse of w. I'm trying to prove that this ... 1answer 63 views ### Prove that this language is not regular I need to prove that the language$$L = \{a^nb^mc^k|n+k\neq3m\}$$is not regular. Any ideas how I can do that? 2answers 338 views ### Can an infinite set of primes be a regular language or CFG? At first glance, it seems like the pumping lemmas should somehow "easily" show that an infinite set of primes (say, written in binary) cannot be a regular language or context-free grammar. But I don't ... 1answer 623 views ### Are languages regular if their concatenation is regular? Let A, B \subset \Sigma^* be languages. If the concatenation product AB is regular, are A and B necessarily regular? I'm inclined to think this is true since the regular language AB has a ... 2answers 390 views ### Pumping Lemma Excercise I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ... 2answers 52 views ### Why is S(L) regular? Let L be a regular language, and \Sigma be its alphabet. Then, the language S(L) = \{y \in \Sigma^*~|~xy \in L \text{ for some string }x \in \Sigma^*\} is also regular. I am trying to ... 1answer 2k views ### Showing that a language is not regular using Myhill-Nerode Theorem I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Thanks in advance. Let Σ = \{0, 1, +, =\} and \mathrm{ADD} = \{x = y + z \mid x, y, ... 2answers 42 views ### Using Pumping Lemma to prove a language not regular I'm currently stuck on a problem were I'm asked to look at a language and prove whether or not it is a regular language or something else such as context-free. I've been given the example: ... 1answer 62 views ### recurrence relation of a language I am looking at the following: Consider a language X which consists of all bitstrings with no more than 2 consecutive zeros (represented by the above automaton). Next consider a sequence s_n ... 1answer 72 views ### Prove that if L is regular then f(L) is regular Prove that if L is regular then f(L) is regular.$$f(L)=\{w: \text{every prefix of $w$ of odd length $\in$ L } \}$$So my attemption is: Let M= (Q, \Sigma, \delta, q_0,F)  will be DFA ... 2answers 152 views ### Prove that the language \{bin(p) \mid p\ \text{is prime}\} is not regular (prime numbers) Prove that the language \{bin(p) \mid p\ \text{is prime}\} is not regular, where bin(p) denotes the binary representation of p. I should use the pumping lemma. But I have a problem. Could you ... 2answers 37 views ### FSM to be regular with atleast two 0's and at most two 1's Is it possible to construct a FSM to prove that the set X is regular, where$$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$1answer 51 views ### Give a regular expression for A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*} and y contains at least k 1's \} The regular expression that is given is 1(0 \cup 1)^{*}10^{*}. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for k = 4) 1111 ... 1answer 63 views ### Working with the word w⋅y, while given the word y⋅w L is a regular language. I am given F(L) such that$$F(L)= \{wy \mid yw\in L\}$$I need to prove that if L belongs to L_\text{dfa}, F(L) also belongs to L_\text{dfa}. I am having a hard ... 1answer 84 views ### proving by construction that language is regular I had this exercise saying the following:$$ L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\} $$I need to prove that L is regular by defining an ... 3answers 3k views ### Is there a subset of a non regular language that is regular I am just curious is there any non regular language whose subset is regular? 2answers 426 views ### Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :( 1answer 38 views ### Proving that the language \mathscr L is non regular using the pumping lemma I need to prove that the language \mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\} is non regular using the pumping lemma For example: ... 1answer 37 views ### proving that a regular language can be accepted by a fast finite automaton Let it be L a regular language. Prove that exists a fast finite automaton (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=<Q,Σ,P,δ,s,A> which: 1. Q is a finite set of ... 0answers 49 views ### Is the following language L regular? L=\{ww^Rv\mid v,w\in \{a,b\}^+\} Is L regular ? Edit Is it ok? Let p will be length of pumping lemma. Then, a^pb(a^pb)^Rv\in L. When a^p(a^pb)^Rv = xyz p\ge |y|\ge 1  So ... 4answers 146 views ### prove that language is not regular (prime numbers)$$\sum_{p\,\in\,\text{Prime}}(cb^*)^p + (b+c)^*cc(b+c)^*$$Show that language is not regular. We see that there are two possibilities: p (prime) blocks of b's separated by c or any string of ... 2answers 69 views ### Determine whether L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\} is regular. Given the alphabet \Sigma=\{a, b\} and for the next Language L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\} determine whether the language is regular. Firstly, I think this language is regular. ... 2answers 132 views ### Pumping Lemma to show a language is not regular Let \Sigma = \{a, b\}. Use the Pumping Lemma to show that \mathcal L = \{ a^pab^q: p < q \} is not regular. Not sure how to apply PL here, if someone can give some direction. 1answer 167 views ### Is this language regular? Given m,n∈Z, A is a finite alphabet set ,and L=\{(a^m,a^n)\}^* is subset of A^*\times A^* . Is this language regular ? For example, is L=\{(a^3,a^7)\}^* regular ? Here L is not the set ... 1answer 92 views ### Algorithm for checking if regular language has given property Give an algorithm that will decide (in any finite time) if given regular language L (given by some regular expression) has given property:$$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq ...
I know to prove a language is regular, drawing NFA/DFA that satisfies it is a decent way. But what to do in cases like $$L=\{ww \mid w \text{ belongs to } \{a,b\}*\}$$ where we need to find it it ...