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
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?
3
votes
2answers
69 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
36 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
31 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
58 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
33 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
31 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
32 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
50 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
55 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
56 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
48 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
120 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
35 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
57 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
34 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 ...
1
vote
1answer
62 views

Proving languages are undecidable

Let L5 be the language { {G,D} | G is a CFG, D is a DFA, and L(D) ⊆ L(G) } Show that L5 is undecidable. Is L5 R.E.? Is it co-R.E.? I am not quite sure where exactly to start with this. Could ...
2
votes
3answers
52 views

regular language proof, a language partial to a regular one

So, I've been trying to solve a question I got and I think I'm correct but I'm not positive. Is the language {w| www belongs to L' and L' is regular} regular? I couldnt find any way to prove it isnt ...
1
vote
1answer
62 views

Equivalence classes in a regular language

Question: Let L be a regular language, ~${_L}$ is it's equivalence relation (as was defined in Myhill Nerode theorem) that divides $\Sigma^* $ to 4 non empty equivalence classes A1, A2,A3,A4. Let ...
0
votes
1answer
12 views

Formal languages problem

What is meant by L1L2 ? Does the n have to be the same for both? So, aabbcc is an element of L1L2 and aabbcccc is not? How about the first problem - Epsilon. Is it an element of L1L2? Since n>0 in L1 ...
0
votes
1answer
70 views

Is this a regular language ? SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2}

Question: Define the following operation: SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2} Let L1 be any language, and L2 regular. Prove that SubString(L1, L2) is regular. Thoughts: I need to somehow ...
0
votes
1answer
27 views

Designing a Pushdown Automation to accept a language

Im a novice trying to understand the theory of computation.Im trtying to learn about PDA.I understand that it is a machine counterpart of CFG.Im basically referring to Introduction to Automata Theory ...
1
vote
1answer
57 views

Automata Language regularity proof by construction.

I've been trying to prove or disprove a question that popped during our last session in Uni, we've been using automaton constructing to prove regularity for a while now and I really do have the handle ...
0
votes
0answers
82 views

Conjunction and XOR of Regular Language to DFA

If you could help me with this homework it would be greatly appreciated. If we assume that $M(i)$ is the finite automaton that recognises the regular language $L(i)$ for $i = 1,2,\ldots,n$, how can I ...
0
votes
2answers
46 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 ...
0
votes
1answer
69 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
0
votes
1answer
76 views

is $\{a^n b^m | n \neq m\} $regular or non regular?

$\left\{a^nb^m\mid n \neq m \right\}\subset \{a, b\}$. I have been asked to prove this is irregular but I think it is regular as I can write a regular expression a*b* for it. Am I wrong? If so how ...
0
votes
1answer
62 views

Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$ So far I have $E \to EcE$ $E \to a$ $E \to b$ $E \to c$ But I'm new at this and feel I'm miles away from a finished answer
0
votes
2answers
55 views

If language L is not regular, and L ⊂ M. Do we know if M is regular or not?

I have been given some questions to do regarding regular/irregular languages. And have the following questions True/False (i) If L is not regular and L ⊂ M, then M is not regular. (ii) If L ⊂ M and ...
1
vote
1answer
230 views

{w| w ∈ {a, b} * is not a palindrome} Prove this language is not regular. [duplicate]

I've been doing some work to prove some languages are not regular. I have previously used pumping lemma to prove by contradiction. However I am used to questions which ask to prove languages such as ...
0
votes
3answers
47 views

How can I prove this language is not regular?

$$\left\{a^{2^n}\mid n \ge 0\right\} \subset \{a\}^*$$ How can I prove this language is not regular?
-1
votes
1answer
48 views

Regular expression with xor [duplicate]

Can anyone help me with this question: I know i asked a similar question not a while ago but i'm not able to understand how its possible. If anyone could give me a lot of examples instead of an ...
0
votes
1answer
21 views

Regular expression problem

I have this question and no clue how to solve. Thanks for your help I need to build the regular expression matching this language $$L=\{ 0^m~1^n | (m+n) \pmod 3 = 1 \}$$
1
vote
0answers
147 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
0
votes
0answers
94 views

Prove that whenever L is a regular language so is HasPrefix(L)

For a language $L$ over an alphabet $\Sigma$, define the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ ...
1
vote
1answer
57 views

How to prove that a language `L` is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
1
vote
0answers
48 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
0
votes
1answer
70 views

How to prove that $ \{ 0^n 1^{5n} : n \ge 10000 \} $ is not a regular language?

I proved that $$ \{0^n 1^{5n} : n \ge 0\} $$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{ 0^n 1^{5n} : n >= 0 \}$ is regular language. ...
0
votes
1answer
21 views

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free I have to prove or give a counterexample. I know the closures properties of CFL, however, this ...
1
vote
1answer
47 views

Show that the language is not regular using Myhill-Nerode Theorem

I saw that similar questions have been answered on this site, but I've been unable to translate those answers to my problem. $$L=\{ww^R\mid w \in \{a,b\}^*\}$$ This is what I tried: BWOC, assume ...
0
votes
1answer
73 views

Question about formal languages, quotient operator L1/L2.

I come across this problem: Consider the following regular languages: $L1=\{a^*b^*c^*\}$ over the alphabet $A=\{a,b,c\}$ and $L2=\{( a b | b b | a )^*\}$ over the same alphabet as above. Find the ...
1
vote
1answer
40 views

Prove regular languages closed under operation by changing alphabet?

Suppose we have the following language operation: $Duplicate(L) = \{Duplicate(w)|w \in L\}$ where if $w=w_1w_2\ldots w_n$ $Duplicate(w) = w_1w_1w_2w_2 \ldots w_nw_n$. It is simple to construct a DFA ...
0
votes
1answer
32 views

Is this language regular? $\{0^n 1^m \mid m \ne n\}$, I don't understand the direct proof by pumping length

There is a direct way to prove it: If $p$ is the pumping length and we take the string $s = 0^{(p)}1^{(p+p!)}$, then no matter what the decomposition $s = xyz$ is the string $xy^{(1+p!/|y|)}z$ will ...
0
votes
1answer
40 views

Pumping Lemma for a regular language

I've done pumping lemma proofs in the past but I'm honestly not even sure where to start on this problem. Using the Pumping Lemma for Regular Languages show that the language $$L = \{a^i b^j c^k ...
0
votes
1answer
37 views

I don't understand the value of the following regular expressions.

$$\begin{align} 0^{*}10^{*} &= \{w ~\mid ~ w \text{ contains a single } 1\} \\ \Sigma^{*}1\Sigma^{*} &= \{w ~\mid ~w \text{ has at least one } 1\} \\ 0 \Sigma^{*}0~\cup ~1\Sigma^{*}1~\cup ...
3
votes
1answer
153 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
0
votes
1answer
31 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...