Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
8 views

Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3

Let $R=(a*)+(b*)$ be a regular expression. Prove that there cannot exist any DFA $M=(Q,\Sigma,\delta , q0, A)$ such that $|Q| = 3$ and $L(M)=L(R)$. The problem is, I think IT IS possible to construct ...
0
votes
1answer
23 views

If R is a regular language, is R³ = R o R o R also regular?

My understanding of a regular language is that for a language to be formal, it must be able to be represented by a DFA or NFA. To prove a language is not regular you can use the pumping lemma to get a ...
1
vote
1answer
32 views

DFA for language of all strings avoiding 'aa'

I'm trying to draw a dfa for this description The set of strings over {a, b, c} that do not contain the substring aa, current issue i'm facing is how many states to start with, any help how to ...
0
votes
0answers
28 views

Did I prove the language is not regular?

I am trying to prove the following language that is not regular. I used Pumping Lemma proof and my proof goes as follows: Assume that L is regular and let p be the constant of Pumping-Lemma. This ...
2
votes
3answers
147 views

Is {a^n: n is a product of exactly two primes} regular?

I am struggling to prove the following question. $L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$ I feel like the language is not regular but I am having trouble proving it. I tried ...
0
votes
0answers
24 views

Proving a language is Not Regular without using Pumping Lemma? [duplicate]

I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction. $$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$ I've seen a ...
1
vote
3answers
64 views

All languages are regular, as unions of singleton languages

We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular. Suppose there is a non-regular language $L$...
1
vote
1answer
31 views

Finite / Infinite Languages True/False and why?

Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why. There are finitely many finite languages. -This is false ...
1
vote
1answer
26 views

How to show that A is not regular?

Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “...
1
vote
1answer
24 views

$A$ nonregular language, is $A\cup B$ nonregular?

I was reading this question; regarding whether $L=A\cup B$ is nonregular if $A$ is. As is rightly pointed out in that answer, there is no simple rule. But what if we imposed the following conditions: ...
2
votes
1answer
205 views

show that if L is a regular, then drop(L) is a regular

I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof. I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I ...
2
votes
1answer
31 views

What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?

In other words, what is the likelihood that a recognizer of a given regular language will accept a random string of length $n$?   If there is only a single non-terminal $A$, then there are only ...
2
votes
1answer
29 views

If DFA has two states, which of the conditions hold?

Let $L$ be a regular language ,and $M = (Q, Σ, δ, q_0, A)$ is a DFA such that $L(M) = L$. Prove that if $|Q| = 2$ then one of the following holds : a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$ The problem ...
2
votes
1answer
93 views

Method to construct a finite state machine for a finite-size language L

I need to define a method to construct a finite automata for a finite language L (part of my proof for something else). My idea: Create $|L|$ accepting states. For each input string $s$ from $L$, ...
1
vote
2answers
34 views

Proving $({L_A}^* L_B)^+ = (L_A \cup L_B)^*L_B$

I'm trying to prove the following identity: $$ ({L_A}^*\ L_B)^+ = (L_A \cup L_B)^*L_B $$ which is clearly true as both sides will exactly match "any sequence of A and B ending with B" : $$ B, AB,...
3
votes
1answer
60 views

Is Palindrome subset of a regular language regular?

Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$, then we know that $M$ contains all half copies of palindrome strings ...
1
vote
1answer
75 views

Proving a language is not regular using the Myhill-Nerode Theorem

I have to prove that the following languages are not regular using the Myhill-Nerode Theorem. $\{0^{n}1^{m}0^{n} \mid{} m,n \ge 0\}$ $\{w \in\{0,1\}^{\ast}\mid w\text{ is not a palindrome}\}$ For ...
3
votes
1answer
58 views

Is LOG(L) Regular? [duplicate]

For a language L $\subseteq$ $\Sigma$* , define LOG(L) = { u $\epsilon$ $\Sigma$* | $\exists$ v s.t. |v| = $2^|$$^u$$^|$ and uv $\epsilon$ L}. Show that if L is regular so is LOG(L). I was trying to ...
0
votes
1answer
41 views

Why is {w | no prefix of w starts with b} = {w | the first character of w is a} ∪ {e}?

\begin{align} L &= \{ w \in \{a, b\}^* \mid \text{ no prefix of $w$ starts with $b$}\} \\ &= \{w \in \{a, b\}^* \mid \text{ the first character of $w$ is $a$} \} \cup \{e\} \end{align} Why ...
0
votes
0answers
51 views

If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

I'm trying to work out a proof by construction that $L/a$ would be regular. $a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
1
vote
1answer
43 views

Automata with minimal number of states using reverse

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...
0
votes
1answer
21 views

Examples of Regular, Context-free and Context-sensitive languages

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...
0
votes
0answers
15 views

Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}

The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and ...
31
votes
2answers
2k views

Planar regular languages

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
1
vote
1answer
35 views

Prove that a language is bounded if and only if it's finite

Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
0
votes
0answers
24 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
8
votes
0answers
57 views

Regularity profiles

A standard exercise in formal language theory uses Lagrange's four-square theorem to construct a language $L$ such that $L$ isn't regular but $L^2$ is regular. (Let $A = \{ a^{n^2} : n \geq 0 \}$. ...
0
votes
0answers
32 views

If $L^2$ is regular. Does that imply L is regular [duplicate]

If $L^2$ is regular. Does that imply L is regular. I think L need not be regular. But I can't find any example where L is not regular but $L^2$ is regular. My teacher told me an example where L={$0^...
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
54 views

How to prove this language is not regular?

I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
0
votes
0answers
25 views

Is there a language that pumps, but is not regular? [duplicate]

I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.
1
vote
2answers
115 views

How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition $$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$ But I dont really know how to apply this information to check whether or not a grammar ...
0
votes
0answers
20 views

A deterministic finite state automata for finding all (potentially overlapping) regular expression matches?

I was working on a bioinformatics practice problem named Finding a Protein Motif on rosalind.info. In essence, I was given a particular regular expression ...
0
votes
1answer
26 views

Condition in Arden's rule

According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string. My question: what is the problem with the ...
1
vote
1answer
68 views

Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

I want to formally write the equivalence classes of the following language: $$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$ I understand the definition ...
2
votes
2answers
199 views

Proof: There exists an irregular language L such that LLLL is regular

As title. I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one. A senior gave me a hint that Lagrange's four square theorem ...
1
vote
1answer
34 views

Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}

I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer ...
-2
votes
1answer
38 views

Regular Expression: Writing an expression with at least two characters in length? [closed]

A past exam question: (1) Consider the language, $L$, of strings over the alphabet $\{x, y\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members ...
-1
votes
1answer
16 views

Is finite subset of a set which contains all non regular languages a regular set?

Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ? I know that A is not recursive enumerable set (undecidable). So I wonder ...
2
votes
1answer
43 views

How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language: If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
1
vote
1answer
55 views

How to characterize equivalence classes induced by Myhill-Nerode theorem?

Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
1
vote
1answer
79 views

Meaning of L* if L is a language

I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
3
votes
2answers
159 views

Converse of pumping lemma for regular expressions

I want to come up with a language that satisfies the pumping lemma while not being a regular expression. I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is ...
0
votes
0answers
18 views

regular expression with kleene closure [duplicate]

my question is if my regular expression R is 1* that means the language accepted is {^,1,11,111,1111...} in that case i don't understand the meaning what (R*)* means
0
votes
1answer
23 views

Counting number of states from a regular expression

Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A ...
1
vote
1answer
24 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
2
votes
1answer
46 views

Is $L(G) \subseteq L(R)$ decidable?

Is the following problem decidable? Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$? It is given that the following problem is undecidable Given a ...
1
vote
1answer
54 views

Can the difference of a non-regular and a regular language be regular?

I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises: If $L_2,L_3$...
2
votes
2answers
56 views

Is the language L = {(a,b)* | #a * #b is an odd number} regular?

Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$ If i'm not mistaken the condition is the same as ...
0
votes
2answers
39 views

Using pumping lemma to prove irregularity of regular language - what is my error? [duplicate]

I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong? L={ab}, ...