Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,743
questions
1
vote
2
answers
68
views
Prove a language created by applying a function on a regular language is regular
Let $L$ be a language over $\Sigma=$ {$a,b,c$}
We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$.
Let $T(L)=${$ T(w) : ...
- 306
2
votes
1
answer
36
views
Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?
Let $L$ be the language of infinite words in $\{0,1\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable?
I think that $L$ is not $\...
- 23
3
votes
1
answer
613
views
Can we transfer every DFA to DFAs with start state having no in edge?
The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
1
vote
1
answer
63
views
Transform a non-regular language into a regular one using sort
Is there a way where sort turns a non regular language into a regular one.
What I mean by sort is this:
Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively.
...
- 13
3
votes
0
answers
49
views
Reference request about equivalence of automata / regular expressions up-to a language
The most widely used notion of equivalence of regular expressions
$r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
- 8,268
1
vote
1
answer
102
views
Regularity or non-regularity of union of two languages
Consider this language:
$K=\{xy \mid x=\{a,b\}^*, y=x^R \text{ or } y=x\}$
I know that these languages are non-regular separately:
$K_1=\{xy \mid x=\{a,b\}^*, y=x^R\}$
$K_2=\{xy \mid x=\{a,b\}^*, y=x\}...
- 11
0
votes
1
answer
49
views
Is pumping lemma not applicable for every 'long enough' string in the language?
I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
- 15
-1
votes
0
answers
25
views
If A is nonregular, then there exists a nonregular language B such that A∩B is infinite
Please provide a short, high level proof if the above statement is True, and a counter example if the statement is false.
1
vote
1
answer
33
views
Is it true that $R.L^* + L^* = R + L^*$?
I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further.
I want to ...
- 15
0
votes
1
answer
44
views
Algorithm to determine the regularity of a language
According to the answer provided by Janoma, there are several methods to determine the regularity of a language.
Theorem
Let L ⊆ Σ∗. The following conditions are equivalent:
L is generated by a ...
0
votes
0
answers
27
views
Pumping length of (a+b)(a+b)*
I'm trying to figure out the pumping length of (a+b)(a+b)*
From what I understand, this means that there is some A or B followed by any number of either A's or B's e.g
ABBBB
or
AAAAA
but AAAABA ...
1
vote
1
answer
25
views
Confusion regarding FLEX(regular expressions)
I am building an analyzer that takes in text and numbers the lines;
taking in
hello how are you
i'm fine thanks
as input and using the code:
...
- 11
0
votes
0
answers
53
views
What is a regular expression that describes whether an integer w is a multiple of 6?
Let's say we are looking at the decimal language $L_6$ where $$\Sigma = \{ 0,1,2,3,4,5,6,7,8,9 \}$$ and $L_6$ accepts an integer w if w is a multiple of 6. I'm trying to find the regular expression ...
1
vote
1
answer
91
views
How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?
Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row.
Let $\Sigma_2 = \left\{
\begin{bmatrix}0\\ 0\end{bmatrix},
\begin{bmatrix}0\\ 1\end{...
- 11
1
vote
0
answers
19
views
Extending minimal top-down tree automata
I'm trying to find an algorithm to update minimal top-down tree automata/hypergraphs.
Regular tree grammars can be seen as definitions for recursive data structures:
...
- 111
0
votes
1
answer
62
views
Operation of non-regular with regular language
Would it be correct to say that on a operation with a Non-regular language (L) with a Regular language will always return the language L?
I'm came across a property that when we intersect a non-...
- 115
1
vote
0
answers
27
views
Which non regular language meets the requirements for pumping lemma for regular languages?
I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
0
votes
0
answers
13
views
Converting regular expression to WS1S formula
Is there a "textbook" procedure to convert a regular expression such as $((0,1)(1,0))^*$ to a formula in WS1S?
- 2,230
0
votes
1
answer
40
views
Does every regular expression describe only 1 language?
If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it
Also, $...
- 305
-3
votes
1
answer
37
views
prove $a^nb^m; n<3m + 2$ is not regular by the pumping lemma
I want to prove this language $a^nb^m; 0 \leq n< 3m+2$ to be not regular by the pumping lemma. This is my attempt, is this a correct way of doing it?
Let's suppose $L$ is regular. Let $s = a^{3k+1}...
-2
votes
1
answer
31
views
regular languages under intersection and union, a bit of confusion to clarify
Let's assume that $L_1 = a^nb^{2n}$ and $L_2 = a^na^{2n}$, knowing that $L_1$ is not regular, and $L_2$ is. We also know that regular languages are closed under intersection and union, and complement. ...
0
votes
1
answer
35
views
prove $a^nb^nc^m; n,m \geq 0$
I proved this language $L = a^nb^nc^m; n,m \geq 0$ is not regular the following way:
Let $L \cap a^*b^* = a^nb^n$
We know that $a^nb^n$ is not regular, and $a^*b^*$ is regular. Thus, if $L$ is ...
1
vote
2
answers
103
views
Prove $a^nb^{n^2+n}$ is not regular by the pumping lemma
I want to prove this language $L=\{a^nb^{n^2+n}:n\in\Bbb N\}$ to be nonregular by the pumping lemma. This is my attempt, is this a correct way of doing it?
Let's suppose $L$ is regular. Let $s = a^kb^{...
0
votes
1
answer
52
views
If $L_1 \cup L_2 \in RE$ does it implicate that at least one of them is also in RE?
This was one of my exam questions and the answer is apparently no.
Can someone explain why because I don't understand.
- 11
1
vote
1
answer
76
views
Is the equivalence problem of a CFG and a FSM decidable?
I have the following problem:
Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
- 15
-2
votes
1
answer
30
views
Is a^n , n = 3j+4k , n>=0, a context-free language?
I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.
- 1
0
votes
0
answers
29
views
Is a^n b^k , 0 <= n <= k^2, a context-free language?
I don't think it's a CFL, but I'm having a hard time using the pumping lemma to prove this. Is there any way I can use homomorphism? Maybe h(a)= a, h(b) = lambda...
If the pumping lemma is more ...
- 1
1
vote
1
answer
50
views
Is $L = \{a^{p^2}\mid p\text{ is a prime}\}$ regular?
By pumping lemma, we choose the word $w=a^{p^2}$ that the decomposing is $[a^sa^ta^{p-s-t}]^p$
such that $u=a^s,v^i=a^t,x=a^{p-s-t}$
$[a^sa^{it}a^{p-s-t}]^p=[a^{p+it-t}]^p$
We choose i=p+1,we get $ [a^...
0
votes
1
answer
27
views
How to make a recursive definition for a given predicate?
I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression:
$r=\emptyset$
$r=\varepsilon$
$r=a:\...
0
votes
1
answer
44
views
Why Regular Grammar is Left/Right Linear?
From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)
But, my question is why it is mandatory?
Can't we ...
1
vote
1
answer
39
views
Check whether a regular expression is correct
I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct?
...
D.W.♦
- 150k
0
votes
1
answer
34
views
Regular grammar such that it rejects keywords
I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable.
Def: A variable can be any combination of characters, ...
- 1
0
votes
2
answers
105
views
If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1.
Is L1 regular under the property that regular languages are closed ...
- 1
0
votes
1
answer
203
views
Using the pumping lemma, show that L = {a b^n c^n | n ≥ 0} is not regular
I've encountered many examples which its format is like: a^n b^n. For this I understand that w = 2n and is pretty straightforward, but what happens in my case? Is w = 1 + 2n? And in this case would |...
0
votes
0
answers
36
views
Complement of a language definition
Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$.
I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M ...
- 37
4
votes
0
answers
71
views
Inverse operation to concatenation for regular languages
I'm currently in need of the inverse operation of the concatenation of 2 regular languages.
Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
- 103
0
votes
1
answer
45
views
Why must 2 distinct strings go to the same state in a DFA?
I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA.
Is it that if there are n words and m states, where there are more ...
- 1
0
votes
3
answers
77
views
Proving L1 ∪ L2 ⊆ L1* L2*
I'm stuck here, how can i prove this:
$$L_1 \cup L_2 \subseteq L_1^*L_2^*$$
$$\begin{array}{rcl}
x\in L_1\cup L_2 & \Rightarrow & x\in L_1^* \lor x\in L_2^*\\
&\Rightarrow &x\in L_1^*\...
1
vote
1
answer
49
views
Shuffle of a DCFL and a regular language
This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".
The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
- 13
0
votes
2
answers
73
views
Regular language under intersection and complement confusion
I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L_1$ and $L_2$ as ...
- 33
0
votes
2
answers
68
views
Language to regular expression to prove it is regular
I'm trying to find a regular expression to describe the following language:
$\{a^n xa^n | n≥1,x ∈ Σ^* \}$
where $Σ$ = {a,b}
So far I've come up with
$aa^* (aUb)^* aa^*$
but I don't think that accounts ...
- 103
2
votes
1
answer
35
views
How to prove that for any words $w_1, ..., w_n$ of alphabet $\{0,1\}$ regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
How to prove that for any words $w_1, ..., w_n$ on alphabet $\{0,1\}$ the regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
- 131
0
votes
1
answer
73
views
0
votes
1
answer
62
views
Show that the the language $L = \{0^kww0^m | k,m \ge 1, w \in \{0, 1\}^*\}$ is nonregular
Caveat. You have to show this specifically by showing there exists an infinite set that is pairwise distinguishable with respect to L.
This question was on a quiz which we had 12 minutes to complete (...
- 1
0
votes
0
answers
28
views
Show non regularity of a language using closure property
Show that the language $\{0^n1^m0^n| m,n\in \mathbb{N}\}$ is not regular using closure properties.
I tried showing this using pumping lemma but I am stuck when it comes to closure properties. Please ...
- 1
0
votes
1
answer
27
views
How to use BNF for {a^n b^n | n>0}
so I know that this language is not regular, however, can you still define the language using BNF? This is the problem:
{a^n b^n |n>0}
0
votes
0
answers
23
views
Regular expression for strings that do not contain the substring $aa$ and contain an even number of $a$'s [duplicate]
I am trying to find the regular expression for the set of strings over the alphabet $\{a,b\}$ that:
do not contain the substring $aa$ and
contain an even number of $a$'s
Such examples include:
$...
- 1
0
votes
1
answer
64
views
Is my DFA optimal?
I designed this FSM graph to demonstrate a DFA that would accept any string that
is of length 5,
must contain a d,
can only have as and/or bs before the d, and
can only have bs and/or cs after the d.
...
- 103
0
votes
1
answer
48
views
Regular Language to Regular Expression
Let's assume I have the following regular language:
L = {1,0}*{010}{1,0}*
I would like to convert this to regex for a program. Would the equivalent regular expression for this be:
((0+1)*(010)(0+1)*)
...
9
votes
4
answers
1k
views
Non-regular language whose prefix language is regular but not the whole set of words
I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...
- 391