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

880 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 ...
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 ...
101 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 ...
8k 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

95 views

39 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 ...
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? ...
469 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 ...
462 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 ...
349 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 ...
136 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.
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 ...
68 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 ...
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 ...
688 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 ...
76 views

### Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
360 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 ...
418 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 ...
65 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?
2k views

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, ... 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 51 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 36 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 ... 1answer 75 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 ... 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 69 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 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 ... 2answers 155 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 40 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 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 y\... 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. ... 3answers 268 views ### Proving a language is regular 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 ... 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 = xyzp\ge |y|\ge 1 $So$a^{p+k}b(a^pb)^...
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 ...