Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
-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 $\...

1
2 3 4 5
26