Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,295
questions
-2
votes
0answers
17 views
symmetrical difference of a regular language
Let R be a regular language.
L is a language
given L∆R is also a regular language.
Is L a regular language?
0
votes
1answer
23 views
Induction details for proof of closure of regular languages under unions
I was reading M. Sipser, Introduction to the theory of computation 3ed. where he presents a proof by construction that the class of regular languages is closed under unions (Theorem 1.25). However, he ...
-1
votes
1answer
32 views
Can an infinite regular language be decomposed in this way?
If $A$ is an infinite regular language, can there exist a finite regular language $B$ such that $A = BB^*$?
-2
votes
0answers
10 views
Prove A={ww| w∈{0,1}* is nonregular using the pumping lemma [duplicate]
Prove A={ww| w∈{0,1}* is nonregular using the pumping lemma.
4
votes
2answers
826 views
If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?
If $L$ is not regular and $ L \subset L_1$, does it follow that $L_1$ is not regular also? Can you please provide an explanation? Thanks in advance.
0
votes
0answers
11 views
How to write regular expression [duplicate]
The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's
Can you guys tell me what is the correct answer for this ?
1
vote
2answers
55 views
Prove the following language is regular?
Assume $L_1$ is a regular language, and define:
$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$
Show that $L$ is regular.
I first tried to prove by showing ...
1
vote
1answer
36 views
Are these REs equivalent?
I have to implement a compiler for a given language as part of an assignment.
The language is kept simple enough such that it can be fully expressed through REs.
My question lies with two of the REs ...
0
votes
2answers
44 views
Generating regular expressions not containing abc
Let sigma = {a,b,c}. How do I generate a language L that does not containg abc?
Any guidance is appreciated!
0
votes
1answer
21 views
Is this FA really equivalent to the given regular expression?
From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$.
So the Automata ...
1
vote
2answers
31 views
Proving a language is not regular using Myhill Nerode Theorem
Let $L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$, show that $L$ is not regular using Myhill-Nerode relation.
I don't know how to show that $L$ has infinite equivalence classes ...
1
vote
1answer
52 views
Converting DFA to Regular Expression Using State Removal
I'm trying to convert the following NFA to a regular expression.
I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
0
votes
0answers
27 views
How to write a regular expression that excludes certain strings? [duplicate]
It's a homework problem.
Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb.
My idea was: construct a regex that matches ...
0
votes
2answers
79 views
Large DFA to regex?
For an assignment for one of my courses, one of the questions is to provide a regular expression for the language:
"the set of strings such that the number of 0’s is divisible by six, and the number ...
0
votes
3answers
93 views
Prove that a language is regular
I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible
to remove zero or more symbols from w so that just the string x remains. For ...
-1
votes
1answer
68 views
“If A is nonregular, then there exists a nonregular language B such that A ∩ B is finite.”?
Is the statement true?
I feel that the statement is true. I want to prove it but I don't know how to start the proof.
Any help would be appreciated.
0
votes
1answer
33 views
Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e
An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^*$, where $\...
2
votes
1answer
104 views
Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive
Question: Let $$S =
\{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape}
\}.$$ Show
that $S$ is r.e. (Turing acceptable) but not recursive ...
1
vote
2answers
23 views
If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?
If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?
I think I found a correct proof for this question but my professor says it ...
0
votes
0answers
37 views
Prove the equivalence between regular expressions (cb*c+cb*b)* and (cc)*+(cc)*(cb)(b+c)*
I need to prove the equivalence of the following regular expressions:
(cb*c+cb*b)*
(cc)*+(cc)*(cb)(b+c)*
using the following equivalence rules:
• (1) (E + F) + G = E + (F + G)
• (2) E + F = F + E
...
-2
votes
2answers
144 views
Is the set of strings with equal number of 010’s and 101’s regular?
Let the language be defined over alphabet{0,1}.
Can you prove this by pumping down?
1
vote
1answer
71 views
Using MyHill Nerode theorem to prove a language is non-regular
The language is $S = (a^nb^m | n \geq m)$.
I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that ...
-1
votes
2answers
121 views
Why L' is not regular?
$$L'=\{ww|w\in L\}$$
I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular.
How can I give such an example if according to closure ...
1
vote
1answer
36 views
Proving the regularity of the following language
I have a question about the following problem:
Prove that the language $\{a^nva^n | v \in \Sigma^*, n \ge 1\}$ is regular over
$\Sigma = \{a,b\}.$
I know that in proving a language is regular I ...
1
vote
1answer
38 views
Distinction between 2 languages.One is regular the other is not
whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states.
given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \...
1
vote
2answers
79 views
Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?
I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
0
votes
1answer
26 views
Can I assume that L1 is regular?
$L_{4},L_{2}$ are regular languages.
given an expression which we know is regular: $L_{4}\cap \bar{L_{2}}\cap \bar{L_{1}}$
May I assume that the language $L_1$ is regular? using closure properties
-1
votes
1answer
37 views
Set-theoretic difference of two languages in CFL - REG
Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds?
$L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG.
$L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG.
$L_1-L_2\in$ ...
0
votes
0answers
42 views
Is this proof for pumping lemma legit?
Prove that $L=\{a^{n}b^{m}c^{k}\mid n\leq(m+k)\}$ is not regular.
I used the pumping lemma as follow:
there exists $n\in \mathbb{N}$
$z=uvw$
$|uv|\leq n , |v|\geq1$
$uv^iw$ is a string in L, so ...
1
vote
1answer
45 views
Use the pumping lemma to show it's not regular
I just learned pumping lemma this week and got confused on this question.
B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$.
Hint: the sequence of Fibonacci numbers get increasingly further ...
0
votes
1answer
23 views
Equivalent regular grammar with minimum number of nonterminals
Given a set of terminal symbols $\Sigma=\{a,b\}$ and a set of nonterminal symbols $N=\{S,A,B\}$ with start symbol $S$, then the two following sets of production rules are equivalent:
$S\to aA$
$A\to ...
0
votes
0answers
93 views
Strings that do not contain 11 as a substring
Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring.
She wrote ...
3
votes
1answer
36 views
Slowest growing upper bound for the minimum length of a complementary prefix regular expression
A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar,
...
-1
votes
1answer
57 views
Is a language regular if a word is in a regular language but the reverse is not?
$$A_1 = \{ x \mid x \in A , x^R \not\in B\}$$
$A$ and $B$ are regular over $\Sigma$.
Is $A_1$ regular?
0
votes
1answer
13 views
How do I prove regular/non-regular with Nerode-Theorem? How to use it?
$L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$
$L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$
I have problems to prove regularity with the nerode ...
0
votes
1answer
58 views
What does {a,b}* for DFA's mean?
For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,...
1
vote
2answers
33 views
In an NFA that recognizes L(ab) where ab is a regular expression, what is the point of the empty string transition?
I'm reading Introduction to Computational Theory by Michael Sipser. He provides the NFA below as one that recognizes the language of the regular expression $ab$.
What is the purpose of the middle two ...
1
vote
1answer
42 views
Design a DFA that recognizes the following language
My assignment asked to design a DFA that computes the language:
$L = \{ w \in \{a,b,c\}^\star | \#_a(w) $ is even, $\#_b(w)$ is odd, $\#_c(w)$ is even}
I have been stuck on this question for 2 ...
1
vote
1answer
45 views
Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars
I’m trying to find a way without just hard coding to create a categorical distribution over all characters given a character but with similar looking ones having higher probability. For example, if ...
1
vote
1answer
47 views
Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I'm trying to proof that the following language is not regular using pumping lemma.
$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I started by stating that:
$|w\bar{w}| =...
1
vote
3answers
82 views
Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular
I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?
This was an exam question from previous year. I looked your ...
1
vote
2answers
53 views
How to prove the language of suffixes of a regular language is still regular?
Prove that if $ L \subseteq \Sigma^\star$ is regular, $L'$ is also regular where
$$ L' = \{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\}$$
I'm new learning formal language and haven'...
1
vote
2answers
87 views
How Intersection of Regular Language and a CFL is a CFL?
CFL is not closed under intersection. That means, if we have L1,L2 of CFL then
L1 intersection L2 is not a CFL
And we know, all Regular languages are CFL. Then ...
1
vote
3answers
125 views
Show that if A is regular, then the subset containing only even language strings, is also regular
A language A, even(A) is the subset of A consisting of those strings in A of even length:
even(A) = { x∈A | |x| is even}
I need to use closure properties show ...
2
votes
1answer
89 views
How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?
I am struggling to answer the following question:
How many different languages over the unary alphabet {a} are
recognized by 2-state DFAs?
According to the textbook, the hint was to first ...
1
vote
1answer
28 views
Algorithm to generate inputs with certain properties, but not accepted by a given regular language
General
Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\...
11
votes
2answers
2k views
Can a DFA have an unreachable state?
I am trying to prove or disprove the following statement:
If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$
So my initial thinking is to ...
2
votes
0answers
71 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
0
votes
2answers
64 views
Kleene star operations
Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{∗}$ and $𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages.
a. If $𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $L_1$.
b.Let $\Lambda \...
1
vote
1answer
41 views
Regular Language - Context Free Language
I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question
Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet
$\...
