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
22 views

converting to regular expression

{w | w can be written as $0^k l 0^k$ for some $k \geq 1$ and for any $l$ in ${0,1}*}$ i.e. 00010111000 can be written as 0^3 10111 0^3 How can I convert this description into a regular expression? ...
1
vote
1answer
45 views

Regular language that has a string that cannot be pumped.

This is a question from a past exam. Consider the language $F = \{w | w \in 0^{*}1^{*}\}$ that is kown to be regular. a) Show that if string $w$ is chosen to be $0^p1^p$, that is a member ...
1
vote
0answers
37 views

Nonregular languages that satisfy the pumping lemma at different strengths

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones) The three versions are as ...
0
votes
1answer
59 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
1
vote
1answer
86 views

disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using pumping lemma for CFL

I am writing something about pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma ...
0
votes
0answers
18 views

Origin of the stable distribution name

Mandelbrot (1963) claimed the name stable distribution comes from Paul Levy work: "...The purpose of this paper will be to present and test such a new model of price behavior in speculative markets. ...
-2
votes
1answer
166 views

CFG with reverse strings

I've been trying to figure this out for a while, and I'm at a total loss: Write a context-free grammar that generates the language $\{x y\ |\ x$ is a string over $\{a,b,c\},\ y$ is a reverse of ...
2
votes
1answer
29 views

Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
0
votes
1answer
28 views

find a regular expression

find a regular expression for w such that it does not contain $ aab $ , where w is the strings of $a$'s and $b$'s . ans: I know how to draw the same question with $ aab $ , but cant understand how to ...
0
votes
0answers
59 views

contradiction of pumping lemma on even palidrome language's completion

I have the language of all the words that are not even length palindromes, or more formally: $L= \{ w: \forall u\in\Sigma^*, w\ne uu^r \}$. And I need to prove that the Pumping Lemma for regular ...
0
votes
2answers
36 views

Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
1
vote
1answer
11 views

Find a state machine or a regex that accept the following language description

The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ...
2
votes
3answers
117 views

Show that the language is not regular using the pumping lemma.

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma. I have done the following: Let $i \geq 1$ $$x = a^i b^i \in L$$ $$|x| = 2i \geq i $$ ...
0
votes
1answer
31 views

Check if it is regular language

I have a language $L = \{ a^i b^j c^k \mid i \geq 1 \land j \geq 1 \land k \geq 1 \land (i \neq j \lor j \neq k) \}$ and how to check if it is regular language? I tried using pumping lemma for ...
-1
votes
1answer
70 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
1
vote
1answer
58 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
0
votes
1answer
48 views

A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
0
votes
1answer
69 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
-1
votes
1answer
55 views

disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
2
votes
2answers
53 views

“The regular languages over $A$ are the homomorphic pre-images in $A^*$ of subsets of finite monoids.”

I'm trying to understand the statement: The regular languages over $A$ are the homomorphic pre-images in $A^∗$ of subsets of finite monoids. which appears in the Wikipedia article on free ...
0
votes
1answer
204 views

Pumping lemma proof of $L = \{a^nb^m \mid 0\leq n<m\}$

Prove the following language is not regular using the pummping lemma $L = \{a^nb^m \mid 0\leq n<m\}$ I tried solving this problem what I don't think I was able to reach an accurate proof. But this ...
2
votes
1answer
42 views

Frequency of Words in Document

I'm trying to figure this out: Would someone care to explain how one would go about using this function? More specifically, I don't understand the interval part, how does one count the intervals? ...
1
vote
2answers
51 views

NFA for $L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}$

Write an NFA to recognize the language $$L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}.$$ I'm not quite sure how to do this question. I don't know how to keep ...
0
votes
0answers
79 views

Pumping lemma for $a^n b^{2n}$

I have this question and i am not sure and trying to solve in both way that is through diagram and expression: Question : Prove that $a^nb^{2n}$ is not regular. contradiction: ...
1
vote
0answers
73 views

Proving irregularity using Myhill-Nerode theorem

I'm trying to prove that the following language is irregular using the Myhill-Nerode theorem $$ L = \{ w\space\epsilon \{a,b,c\}^* | \#_b(w) > (\#_a(w) + \#_c(w))! \} $$ While it's completely ...
0
votes
1answer
26 views

Prove that a language is not regular.

I want to ask how to prove the following language is not regular using closure properties. I tried to use pumping lemma but I find the proof itself shaky. I'd appreciate if you can help. The ...
1
vote
2answers
765 views

pumping lemma: ww^R not regular

I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma. Let $p$ be the pumping length and $s = a^pbba^p$. $x = \epsilon$, $y = ...
2
votes
2answers
173 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 ...
0
votes
2answers
46 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
0
votes
1answer
17 views

Finding a Regular Expression with a Specific Length from a language

Given this language, I was supposed to find the Regular Expression that represented it. Having given up and getting the answer later (below) I couldn't understand the regular expression. Given ...
0
votes
2answers
27 views

Why cant this be a Regular Language?

Given L - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$ How can I prove that L is not a regular language?
2
votes
2answers
45 views

Regular Expressions Help [duplicate]

I need a little help with Regular Expressions. The allowed operations are obviously + (union) , * (Kleene star) and concatenation. I have to write Regex for the following 2 examples. I have tried a ...
1
vote
2answers
106 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 ...
1
vote
2answers
30 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}\}\ ? $$
0
votes
1answer
51 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
0
votes
1answer
40 views

Can any Language that is generated LL1 Grammar is regular.?

I have a question is every language generated by LL(1) grammar is regular? I know that every regular language can be generated by LL(1) grammar.
1
vote
2answers
43 views

Closed regular languages

Are regular languages closed under the following construction? $f(L) = \{w \mid w \in L$ and for all prefixes $x$ of $w$ it holds that $x \notin L$ $\}$
1
vote
0answers
65 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
1answer
85 views

Is there a prefix-free regular language whose set of proper prefixes is not regular

Is there a regular language $L$ such that the language $$L^\prime := \{ w : w\text{ is a proper prefix of a word in }L \}$$ has the following properties: $L^\prime$ is not regular, and $L^\prime$ ...
1
vote
1answer
25 views

Subset of regular languages

Assume $L_1$ and $L_2$ two regular languages, and $L_1\subseteq L\subseteq L_2$. Does this imply that $L$ is a regular language? Thanks in advance.
1
vote
1answer
44 views

Name for grammars with rules $A \to uA$

Recall that a right-linear grammar is a grammar that consists of rules of the form $A\to uB$, where $A$ and $B$ are non-terminals and $u$ is a (possibly empty) word of terminals. Similarly for ...
1
vote
1answer
126 views

Prove or disprove whether the following is a regular language

I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ...
1
vote
3answers
68 views

Prove that this language is not regular (Pumping Lemma)

Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
1
vote
1answer
48 views

Is $L=\{w\mid \text{ same number of 010 and 101}\}$ regular?

I tried to prove that this language is regular using NFA or regular expressions and didn't succeed. I would like to see some solutions
0
votes
1answer
93 views

Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
0
votes
1answer
46 views

Prove L is not a regular language (A Finite State Automaton cannot accept it)

$$\mathscr L = \{x \in \{0,1\}^* \mid \text{there is a } y \in \{0,1\}^* \text{ such that } x = yy\}$$ How can I prove that this is not a Regular language? I tried using proof by contradiction but ...
1
vote
2answers
204 views

How to solve pumping lemma questions?

I am trying to prove that L = { aNbMaN-M|N>=M>=0} is not regular using the pumping lemma. I am pretty confused how to solve this. What I have so far (which I am not sure is right) is: Assume L is ...
1
vote
1answer
53 views

Checking some Regular Expression problems

I'm given the alphabet $$ \Sigma = {\{a,b}\} $$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ...
1
vote
1answer
25 views

How to prove the following related with regular languages

How can we prove the following. If $$\sum$$ is any alphabet and L is any language $$L \subset \sum*$$ Then L*L* = L* ?
2
votes
2answers
74 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...