Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,201
questions
0
votes
0answers
16 views
Turing Machine Decidability
Consider the function f that maps strings over {a, b, c} to strings over {0, 1} by replacing
each a by 0, each b by 0, and each c by 1. For example f(cabbc) = 10001. The function f
extends naturally ...
0
votes
0answers
25 views
Regular expression for set of strings with no two consecutive 1's? [duplicate]
I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's.
I'm also wondering if there is a pattern that could be extended to ...
3
votes
1answer
103 views
How do I solve these questions regarding homomorphism?
Questions:
Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
-1
votes
1answer
45 views
Constructing a DFA of strings that are in A but not in B
I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}
I am not really sure where to even start with this one, ...
0
votes
0answers
43 views
If L is a regular language, how to show that cut(L) is not necessarily regular? [duplicate]
Given that L is a regular language. How do I show that cut(L) = {ac | abc ∈ L and |a| = |b| = |c|} is not necessarily regular?
My thought process is that this problem can be re-written as:
cut(L) = {...
3
votes
1answer
40 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 ...
2
votes
1answer
218 views
If R is a regular language, is $R^3= R \circ R \circ 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 ...
0
votes
1answer
42 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
31 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
225 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
28 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
69 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
34 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
30 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
25 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
221 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
31 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
100 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
70 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
79 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
60 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
57 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
22 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
16 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
36 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
58 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
57 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
134 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
205 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
36 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
39 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
44 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
81 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
167 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
24 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 ...
