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

0
votes
0answers
44 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
42 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
26 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
11 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
2answers
31 views

How to Solve Complex Non-Regular Language? [closed]

$L_5={\{ c^n a^m b^p,n+m=p,p≥6}\}$ where $∑=(a,b,c)$ I need little help, I was practicing Pumping lemma, and I encountered this language, I saw these conditions and I got totally confused, what to do ...
-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
43 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
42 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
41 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
37 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
35 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
90 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
117 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
61 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
56 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
64 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
54 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
33 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
30 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
50 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
4answers
44 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
108 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
38 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
42 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?
3
votes
2answers
63 views

Is the language “substrings of an even-lengthed regular language” also regular?

I want to prove that for a regular language $L$ where $\forall w \in L$ the length of $w$ is even, the language containing the first halves of the words of $L$ and the language containing the second ...
0
votes
1answer
34 views

Contruct an NFA

Construct an automaton that recognizes the following language of strings over the alphabet {a,b}: {a,bb} that is only a and bb Do anyone think that this might be the right approach or has any ...
0
votes
1answer
32 views

Regular Expression of alternative 0's and 1's?

Let $L$ be the language of $0$'s and $1$'s in alternate positions, where $$ L = \{ \epsilon, 0, 1, 01, 10, 01010,\ldots\}. $$ Is $(0)*$ + $(1)*$ a valid regular expression that represents this ...
0
votes
1answer
28 views

Regular Language Proof: Union Implication

This is a problem in a theory of computation book that's stumping me: Suppose that we know that L1 ∪ L2 and L1 are regular. Can we conclude that L2 is regular? Explain. At first, I thought I could ...
0
votes
1answer
56 views

How can be proved that $L = \lbrace{ a^n b^m \mid n \le m \le 2n \lor m \le n \le 2m \rbrace}$ is not a regular language?

Prove the language is not regular: $L = \lbrace{ a^n b^m \mid n \le m \le 2n \lor m \le n \le 2m \rbrace}$. I want to use the pumping lemma but I don't know which parts of the string to split up ...
1
vote
1answer
29 views

Pumping lemma shows non-regular language, assignment suggests it is regular

In the assignment it asks us to show that $$ L = \{0^kw0^k \mid k \ge 1 \text{ and } w \in \{0, 1\}^\ast\} $$ is regular (suggesting that it is in fact regular). I don't believe that it is, so I ...
0
votes
1answer
27 views

Closure properties between 2 languages of different types

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
2
votes
1answer
26 views

Concatenation of regular languages.

The concatenation of $L_1$ and $L_2$ denoted by $L_1.L_2$ = $\{uv|u\in L_1\,and\,v\in L_2\}$. If, $$L_1=\{a^n|n\geq0\}\,and\,L_2=\{b^n|n\geq0\}$$ Then why is $$L_1.L_2\neq \{a^nb^n|n\geq0\}$$ I am ...
1
vote
1answer
23 views

Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular.

$\ \sum= \{a,b\} $ Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the ...
1
vote
1answer
45 views

Difference between $\phi$ anf $\epsilon$ in regular language.

What is the interpretation of both $\emptyset$ and $\epsilon$ in a regular language? Do they both mean empty sets? If so then why is $\emptyset^*=\epsilon$ , $\emptyset^+=\emptyset$ and ...
0
votes
1answer
54 views

Regular Language Problem?

Let L be the set of all strings that are not in the English language. Is L regular? From textbook, would like some help? Someone recommended to me to think about how regular and regular languages ...
0
votes
1answer
54 views

Determining if language is regular?

Let $R$ be a regular language and $R_e := \{w\ |\ w \in R \text{ and the length of } w \text{ is even}\}$ Question: Is $R_e$ regular? Prove your answer. I am having trouble with these type of ...
1
vote
1answer
46 views

proof DFA defines same language as minimal DFA

Given a $DFA = (Q, \Sigma, \delta, q_s, F)$ and a minimal $DFA_{MIN} = (Q_{MIN}, \Sigma, \delta_{MIN}, q_{s_{MIN}}, F_{MIN})$ where $Q_{MIN} = \{Q_i \in \mathcal{P}(Q) \mid \forall p,q \in Q_i:p ...
0
votes
3answers
86 views

Language of prefixes of regular language is regular.

Let $L$ is regular language and $L_1$ be the language of all words whose prefixes are all in $L$. I need hint to prove that $L_1$ is regular.
1
vote
0answers
31 views

Why is $a^nb^n|n\geq1$ not regular and $a^nb^n|n\leq {10^{10}}$ regular?

I've heard somewhere that since the latter is bounded, it is regular. Can anyone explain me what a bound actually means? And if the latter is regular, then how would you write the regular expression ...
0
votes
2answers
35 views

complexity of equivalence of two star-free regular expressions

Given regular expressions s,t that do not contain the Kleene star $.^*$, what is the complexity of deciding whether they define the same language? I am sure this can be done in NP-time; but is it ...
1
vote
2answers
31 views

Did I find the right expression for the regular language for this FSA?

I have the following FSA, and the regular language that I found for it: Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally ...