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.

learn more… | top users | synonyms

2
votes
2answers
43 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
1
vote
1answer
48 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
0
votes
1answer
18 views

Regular expression. Proof.

Let $A = \{a,b,c\} $ be an alphabet. Let $\alpha $ be a regular expression. And: $$ 1) \epsilon \in \alpha \\ 2) a\alpha \subset \alpha \\ 3) b\alpha \subset \alpha $$ Prove, that: $$(a+b)^* \subset ...
0
votes
1answer
67 views

How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

How to prove the language of all binary numbers that are prime is not regular using pumping lemma? I have seen Can an infinite set of primes be a regular language or CFG? We have not studied the ...
2
votes
1answer
38 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 ...
1
vote
0answers
61 views

Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ $M'=(Q', ...
0
votes
1answer
29 views

Understanding pumping lemma - length $p$ - in connection with other thread

I create this thread in connection with Is the following language $L$ regular? I would like to show you why I dont understand where I am wrong. I would like to ask question: $p$ - length of pumping ...
2
votes
0answers
65 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
4
votes
2answers
156 views

Language with error.

Let $L \subset \{0, 1\}^∗$ be regular language. $$L_e = \{ w | w = uxv, x \in \{0, 1\}, u\overline{x}v \in L\}$$, where $\overline{x} = 1 − x$ Prove $L_e$ is regular language. For example: If $10 ...
1
vote
1answer
22 views

construction for proof of regularity of language

$L$ is regular. $L'=\{vw:v\in L, w\notin L\}$ Show that $L'$ is regular. I ask you for controlling my construction: $M=(Q,\Sigma,\delta, q_0,F)$ for $L$ $M'=(Q,\Sigma,\delta', (q_0, F') $ ...
1
vote
1answer
48 views

$L$ is regular. Show that $Root(L) $ is also regular

Let $Root(L)=\{w \mid \exists {n\in \mathbb{N}} \text{ such that } w^n\in L\}$. How to deal with it ? I tried think about modifications connected with automat for $L$, but it failed. Help me, please.
0
votes
1answer
116 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 ...
1
vote
1answer
39 views

Regular language. Proof

Let $L$ be regular language over $\{0,1\}$. Prove that $L'$ is also regular: $$L' = \{ w | w \in L \mbox{ and among words of length |w|, w is the least in lexicographic order.} \}$$ To explain, for ...
2
votes
0answers
27 views

Is it true that if $Cycle(L)=\{uv:vu\in L\}$ is regular then $L$ is regular [closed]

Is it true that if $Cycle(L)=\{uv:vu\in L\}$ is regular then $L$ is regular ? Any clues ?
1
vote
1answer
29 views

Difference between regular and not regular languages

I don't understand the difference, in classes I've seen the pumping lemma for regular languages and I know how to apply it to demonstrate whether a language is regular or not, but I feel that I don't ...
0
votes
0answers
25 views

construct automat for language $Cycle(L)$

We have automat $A$ for language $L$. Construct automat for $Cycle(L)$ where $Cycle(L)=\{uv:vu\in L\}$. I have a problem with this exercise. Help me, please. Edit $A = (Q_A, \Sigma, \delta, q_0, ...
1
vote
1answer
72 views

Clarification of the statement of the Pumping Lemma

In class we were told that Pumping Lemma states: "Let A be a regular language over $\Sigma$. Then there exists k such that for any words $x,y,z\in\Sigma^{*}$, such that $w=xyz\in A$ and $\lvert ...
0
votes
1answer
14 views

operations which are closest under regularity - other seeing

We have: $L_1, L_2, $ regular and $L_3$ irreguar. Now: $L_1\cap L_2$ is regular. $L_1\cap L_4 = L_3$ Can I say that $L_4$ is irregular ? The same question about $\cdot, \cup$
0
votes
0answers
45 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 ...
1
vote
1answer
22 views

How to show that a language is regular?

Let $L$ be a regular language over $\Sigma$. Show that: $$\left\{ x_1x_2 \dotsm x_k \mid x_1,x_2,\ldots , x_k \in \Sigma, \exists y_1, y_2, \ldots, y_k \in \Sigma: x_1y_1\dotsm x_ky_k \in L ...
0
votes
1answer
44 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
0
votes
0answers
31 views

How to prove that Pumping lemma can't be used to prove regular languages.

I need a prove that pumping lemma can't be used to prove regular language. Pumping lemma is only used for proving non-regular language, but I need to show that how it can't be used to prove regular ...
0
votes
0answers
12 views

regularity of language $D(L)$, $L$ is regular

Show that $D(L)$ is regular, $L$ is regular. $D(L) = \{w|w\in \Sigma^* \wedge ww^R\in L\}$ Let assume that M has only one state accepting. Therefore, $M'$ has only one state start. ($M'$ recognizes ...
1
vote
0answers
25 views

prove that language is regular (other language is regular)

Let $L$ is regular. Prove that $L'$ is regular. $ L'=\{uv: u\cdot rev(v)\in L\}$ $rev(v)=v^{-1}$ Idea: $L^{-1}$ is regular and recognized by $R$, and $L$ by $M$. Let's assume that $M$ is NFA such ...
-1
votes
1answer
35 views

Isomporphism two languages.

Let $A$ be an alphabet. Let $X,L \subset A^*$ $L$ is regular. Let $$X^{-1}L := \{ w \in A^* \mid \exists x \in X\ \ xw \in L \} $$ $$LX^{-1} := \{ w \in A^* \mid \exists x \in X\ \ wx \in L \} $$ ...
0
votes
1answer
43 views

find automata that accepts following language

Find automata, that accepts following language: $L\subseteq\{0,1\}^* $ $$L=\{w|w\ \text{dosen't contatain four 1's in 7 consecutive symbols}\} $$ My only proposition is: It is only fragment, but it ...
1
vote
1answer
44 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 ...
1
vote
0answers
46 views

Prove that language is regular given other regular language

Let $L\subseteq A^*$ be regular. Prove that $L'$ is regular where $L' = \{vw \mid \exists u\in A^*\ vuw \in L\wedge |u|=|w|+|v|\}$ Help me please. It is very hard for me, I don't know how to start. ...
0
votes
1answer
44 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
1
vote
1answer
46 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: ...
3
votes
1answer
36 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 ...
1
vote
1answer
95 views

Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular

Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular. I have tried for a long time, but I haven't managed to solved it. Someone help me ?
2
votes
2answers
165 views

Are there two non-regular languages whose concatenation is regular?

Here is my proof: Consider non-regular languages $$L_1 = \{a^i b^j | i \neq j\} $$ and $$L_2 = \{b^n a^m | n \neq m\}$$ Then the concatenation of these two languages would be $$L_1 L_2 = \{a^i ...
1
vote
2answers
69 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 ...
3
votes
0answers
60 views

Is regular following language?

I try to prove that the language $L$ is not regular: $$ L = \{w\in(a+b)^*:\#_a(u)>2009\#_b(u)\ \text{for every nonempty prefix u of word w} \} $$ Note: $\#_a(u)$ means the number of symbols $a$ ...
0
votes
4answers
73 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 ...
0
votes
1answer
56 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
0
votes
1answer
20 views

Clarification on Lemma problem

I have trouble understanding this question. I have no idea where to start. Let $A$ be the set of palindromes over $\{a, b\}$. Suppose you are trying to prove that $A$ is not regular using the ...
2
votes
0answers
38 views

show that language is regular

Let $B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each $n\ge 1$ the $B_n$ language is regular. My proposition of solution: What about it ?
1
vote
3answers
50 views

Show that a language is regular

Show that language $B$ is regular: $$B = \left\{1^ky\mid y\in \{0,1\}^*\right\} $$ $y$ contains $\ge k$ symbols $1$ So I try in following way - I'll draw DFA: What about my solution? Is it good?
1
vote
1answer
35 views

Show that the language is regular - Closure

For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $$L=\{w \ \mid \ w=a_1 b_1 \dots a_k b_k, \text{ where } a_1 \cdots a_k \in A \text{ and } b_1 \cdots b_k \in B, ...
0
votes
1answer
32 views

Show that the language is regular

Let $$B_n=\{a^k \ \mid \ k \text{ is a multiple of } n\}$$ Show that for each $n \geq 1$, the language $B_n$ is regular. $$$$ Could you give me some hints how we coukd show this?? Do we have ...
0
votes
1answer
32 views

Construct the DFA of the language

I have to construct a DFA for the language $$\{w \mid w \text{ has exactly two } a's \text{ and at leat two } b's\}$$ To construct it we have to construct first the DFA's for the languages $$\{ w ...
0
votes
2answers
55 views

Checking Understanding of DFA Regular Operations - Intersection and Star

I'm currently taking a Logics course, and trying to understand the regular operations, intersection and star. I have a question regarding the work I have done so far. Given the following ...
-1
votes
1answer
53 views

$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$ [closed]

Why the following is not context free? Anyone could describe it for me. $L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$
0
votes
5answers
59 views

Regular Expression for Simple Language

I'm having trouble writing a regular expression given the following $\{a, b, c\}$ which produces the set of strings of length 3. I don't really understand how to restrict the length of the string. ...
0
votes
1answer
111 views

Context Free Grammar and some details [closed]

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free). S -> SBA | a BA -> AB aA -> aaB B -> b
0
votes
1answer
40 views

Prove the following context-free language is generated by this grammar.

I would like to prove the context-free language $$ \mathcal{A} = \{ w\#x ~:~ w^R \text{ is a substring of $x$ for } w,x \in \{0,1\}^* \}, $$ has the context free grammar \begin{align*} ...
0
votes
1answer
43 views

Prove the following language is context free

I can find many proofs for how a language is not context free using the pumping lemma. But I am not sure how to definitely prove a language is context free. Consider this language: $$\mathcal{A} = \{ ...
2
votes
1answer
44 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?