Questions tagged [regular-language]
Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.
1,232
questions
0
votes
0
answers
19
views
Proof that $L =$ {$a^p : \text{p is prime} $} is not regular
I know that this question has already been answered but the proofs provided do not seem intuitive to me and I propose one using Wilson's theorem.
Say $L$ is regular and its pumping length is $p \geq ...
0
votes
0
answers
27
views
prove using Nerode law that a language is regular
prove that the language πΏ = {π€ β Ξ£β|β1 β€ π β€ π: #ππ(π€) β€ π }, where πΏ is defined over Ξ£ = {ππ | 1 β€ π β€ π} is regular using Nerode law.
basically the string w has, at most, π occurrences ...
- 1
2
votes
0
answers
45
views
Prove that L = {$wβ${a,b,c}$^*$|w contains "abc"} is regular with Nerode theorem?
How to prove that $L = \{w \in \{a,b,c\}^* \mid w \text{ contains } abc \}$ is regular using the Nerode theorem?
Attempt
If I show that there are a finite number of equivalence classes for this ...
- 53
0
votes
1
answer
43
views
Prove or disprove that L = {$a^nb^m$ | $m β 3n + 5$} is a regular
How can I prove or disprove that $L = \lbrace a^nb^m$ | $m β 3n + 5 \rbrace$ is a regular language?
Attempt
Assume $L$ is regular, then its complement $L^\complement$ is also regular.
$L^\complement ...
- 53
0
votes
1
answer
25
views
Is the following language is regular, context free, and/or decidable?
Given a language determine if it is regular, context free, and/or decidable. No proof needed, but an explanation would be appreciated.
A = {a^n b^(2n+6) | n >= 0}
My first guess is no its ...
- 13
-3
votes
0
answers
65
views
Is 0^{3n} equal to 0^30^n?
Fairly simple question I am trying to resolve in my brain. Assume that n is in the set of natural numbers, N.
If given, $$0^{3n}$$ is this equivalent to $$0^n0^3$$
If so, can you say that $$0^{3n}1^{...
- 1
0
votes
1
answer
66
views
Is the algorithmic problem for regular languages decidable?
I have an algorithmic problem, where I need to build an algorithm and say if the problem is decidable. Here it is:
Regular languages $L_1$, $L_2$, and $L_3$ are given by finite automata. Is the ...
1
vote
1
answer
29
views
How can I determine the language from a DFA?
I was given three DFAs to solve.
I understand the first one is a*. I think the second one would be b*(a+)*.
I cannot figure out what the third one would be, it seems like there are too many different ...
- 11
-1
votes
0
answers
10
views
show that L={a+b=c: a=1^n,b=1^m,c=1^(n+m) } is not regular using pumping lemma
Show that L={a+b=c: a=1^n,b=1^m,c=1^(n+m) } is not regular using pumping lemma.
I tried to demonstrate this but I don't really understand how I can do it, can you help me?
- 1
1
vote
1
answer
49
views
Prove equivalence of two regex using basic identities.
I'm trying to prove the following identity
$$
(x+y)^* = (x^*y)^*x^* = x^*(yx^*)^*
$$
Using the following 12 identities
$L + M = M + L$
$(L + M) + N = L + (M + N)$
$(LM)N = L(MN)$
$\emptyset + L = L + ...
- 343
1
vote
0
answers
82
views
Is Pumping lemma so useful? (Michael Sipser "Introduction to the Theory of Computation 3rd Edition")
I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser.
Pumping lemma is the following proposition:
THEOREM 1.70
Pumping lemma If $A$ is a regular language, ...
- 8,004
1
vote
1
answer
28
views
Infinite number of regular exressions for a given language
Took a Theory of Computation exam where one of the questions was :
Is there an infinite amount of regular expressions for the language $L=\{aa,bb\}$ ?
The proof requested was just an informal one.
My ...
0
votes
0
answers
40
views
regular languages and suffixes
Let $\Sigma$ be a finite alphabet. For a language $L \subseteq\Sigma^*$ we define:
$$Suff(L)= \left\{x\in\Sigma^*| \exists u \in \Sigma^*, u\cdot x \in L\right\}$$
Show an example of a language $L$ ...
- 37
0
votes
1
answer
47
views
Build automata for words with both "bab" and "abb"
I have two finite automata, one for words containing "bab" and one for words with "abb."
I wish to build automata that represent the multiplication of both (words with both "...
- 3
1
vote
1
answer
75
views
Using pumping lemma show that language $L = \{a^{n^2} | nβ₯ 0\}$ is not regular.
Using pumping lemma show that language $L = \{a^{n^2} | nβ₯ 0\}$ is not regular.
Is this approach correct?
Let's assume that $L$ is regular so then the pumping lemma applies.
Let $w = a^{n^2} β L$.
We ...
1
vote
0
answers
35
views
The connection between regular languages and formal power series
Is there a characterization of the regular languages involving formal power series? I saw $\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$ and $A^* = \epsilon + A + AA + AAA + \cdots$ in two different contexts on ...
- 2,413
0
votes
0
answers
21
views
Myhill Nerode Theorem equivalence classes
Let L = {{a,b,c,d,e}* | each letter of alphabet appears exactly once in the word}. Prove that L has at most 40 and at least 10 equivalence classes. Also, find an estimate for general k.
My approach: ...
- 199
-2
votes
1
answer
52
views
Determining whether a given language is regular
Suppose language $L = \{\,a^{i} b^{k} : k \text{ divides } i\,\}$.
Some strings in $L$ include β¦
$\,a^{0} b^{1} = b \in L\,$ since $1 \text{ divides } 0$
$\,a^{1} b^{1} = ab \in L\,$ since $1 \text{ ...
- 151
1
vote
0
answers
35
views
Regular Expression Identities list?
I have been working on problems to simplify or equate certain regular expressions to others but so far the list of identities I have found in my textbook (Sipser) doesnβt tell me enough to simplify ...
- 294
1
vote
2
answers
157
views
Finding the set of strings over {𝑎,𝑏} that ends with an odd number of "a"s
I need to write a regular expression that identifies the set of all
possible strings over Ξ£={π,π} that end with an odd number of "a"s.
I'm getting better with regular expressions, but ...
- 119
0
votes
0
answers
75
views
Regex groups and complements
Not sure about the "math" language of that but ill try to explain my question:
Assume we have two regexes A, B. I say Regex ...
- 1
-2
votes
1
answer
80
views
are two sets of infinity necessarily equal | Automata
we'll define the relation $\equiv_L$ (same one as the one in Myhill-Nerode theorem) as follows:
there exists two string $x,y$ and a language $L$ under the $\Sigma$ alphabet
$x\equiv_Ly$ if there $\...
user956293
1
vote
1
answer
57
views
Proving a class of languages is closed under union when it closed under concatenation, (inverse) homomorphic images, and intersections.
Let $C$ be a class of languages closed under concatenation ($\cdot$), intersection, homomorphic images, inverse homomorphic images, and intersection with regular languages. Prove that $C$ is also ...
- 1,920
0
votes
0
answers
33
views
What is the language generated by this grammar?
S β 0A | 1B | Ι | 0
A β 0A | 0S | 1B
B β 1B | 1 | 0
I've tried to find some specific properties of some of the generated words, but I've failed.
- 37
0
votes
0
answers
53
views
Proving Language is Non Regular With Pumping Lemma [duplicate]
I have the formal language $Z$ over the alphabet $Q \{a, b, c\}$ and it is generated by the context-free grammar whose non-terminals are $S, A$, and
$B$, the start symbol is $S$, production rules are ...
- 63
-1
votes
2
answers
66
views
Proving Language is Non Regular Using Pumping Lemma
I am working on a question where I have the formal language Z over the alphabet Q {a, b, c} and it is generated by the context-free grammar whose non-terminals are S, A, and
B, the start symbol is S, ...
- 63
0
votes
1
answer
25
views
Regular expression extraction from alphabet
I have this Alphabet Ξ£ = {k,l} so I do not understand how I can find the words equal bigger than 3
β€3 in L ((k|l)l*), should I use the words with 3 letters always starting with k or somthing else?
- 3
0
votes
1
answer
29
views
Proving that $B(L)$ is regular if $L$ is regular
$L$ is a binary language.
$$B(L) = \{ w | w β L \text{ and }|w|>10 \}$$
I need to prove the following:
If $L$ is regular $\rightarrow$ $B(L)$ is regular
I thought about doing it using Nerode's ...
user956293
0
votes
0
answers
42
views
Which language will be generated by the following grammar?
So i have
$$ G = (V,\sum, S, P) $$
while $$ V = {S, A, B} $$
$$ \sum = {a,b,c}$$
and for P:
$$ P:= \begin{cases}
S \rightarrow & cA\ | \ bB, \\
A \rightarrow & c, \\
B \...
- 331
0
votes
1
answer
63
views
Algorithm to determine if $L_1$ is a subset of $L_2$ in Automata Theory
I need to create a pseudo Algorithm to determine if $L_1$ is a subset of $L_2$ where both are regular languages with a given DFA.
I thought about creating the intersection automaton of $L_1$ and $L_2$ ...
user956293
0
votes
1
answer
58
views
Proving irregularity using Myhill-Nerode theorem
I need to prove that L = { 0^(3n)1^(2n) | n>0 } is irregular using The Myhill-Nerode theorem
I understand I need to demonstrate that it is not a finite union of ...
user956293
0
votes
1
answer
72
views
Create regular expression not contain "aaa"
I have a question about creating regular expression out of the given language.
The language is : πΏ3 = {π€β{π,π,π}β|π€ ππππ πππ‘ ππππ‘πππ πππ}
I'...
- 9
0
votes
1
answer
25
views
Regular language: what is the Union of the iteration of 0's with the iteration of 1's
I'm taking the Edx Stanford compiler course and it shows
$0*$ + $1*$ = $(0^i | i >= 0)$ u $(1^i | i >= 0)$
Sorry screen readers but in case my mathjax is illegible.
In the second line it shows ...
- 224
0
votes
0
answers
56
views
prove $a^nb^{n^2+n}$ is not regular by intersection
I want to prove that this language is not regular $L = a^nb^{n^2+n}; n \geq 0$
It proved a bit challenging to prove it directly, and thus I am looking for the intersection way.
I want a regular $L_1$ ...
- 481
1
vote
2
answers
82
views
If $L_1L_2$ is regular language, is $L_2L_1$ regular as well?
If $L_1L_2$ is regular language, is $L_2L_1$ regular as well?
I think the answer is no, but I'm not sure how to contradict.
- 377
-3
votes
1
answer
49
views
Numerical values for chance words. [closed]
We use probabilistic words such as "likely", "unlikely" and so in normal conversation. I would like for these rather vague notions to be given some mathematical precision. As a ...
- 214
2
votes
0
answers
66
views
Prove $NOTCONTEXTFREE_{TM}$ is not recursively enumerable?
$NOTCONTEXTFREE_{TM}$ = {$\langle M \rangle$, M is a turing machine and the language of M is not context-free}.
I'm trying to prove the language $NOTCONTEXTFREE_{TM}$ is not recursively enumerable. I'...
- 33
1
vote
1
answer
59
views
Determine if language $L=\{xyxz\,\,|\,\,x\neq\varepsilon,\,\,x,y,z\in\{0,1\}^{*}\}$ is regular
Question.
Determine if the language is regular:
$L=\{xyxz\,\,|\,\,x\neq\varepsilon,\,\,x,y,z\in\{0,1\}^{*}\}$
I think $L$ is non regular, because of the second x.
I'm trying to prove with the ...
- 377
0
votes
1
answer
40
views
Determine if language is regular
Question.
Determine if the languages are regular:
$L_{1}=\{(ab)^{k}a(ba)^{k}\,|\,k\geq0\}$
$L_{2}=\{(ab)^{k}b(ba)^{k}\,|\,k\geq0\}$
I think both are not regular, I used the Pumping Lemma to prove, ...
- 377
0
votes
1
answer
61
views
Prove that the language is not regular without using the Pumping Lemma
Question.
Prove that the language is not regular without using the Pumping Lemma:
$L=\{a^{n}b^{m}c^{k}\,\,|\,\,n^{2}+m^{2}=k^{2}\}$
Attempt.
I assume that L is regular, and I am trying to use ...
- 377
0
votes
0
answers
43
views
Find regular expression for a given language $L=\{0^{n}1^{m}\,\,\,|\,\,\,n+m(mod3)\neq0\}$
Question.
Write a regular expression for the language:
$L=\{0^{n}1^{m}\,\,\,|\,\,\,n+m(mod3)\neq0\}$
Attempt.
$r=(000)^* (0(Ξ΅+0+1+011)+1(Ξ΅+1)) (111)^*$
Is my regular expression correct? If so, is ...
- 377
0
votes
0
answers
117
views
Complement of a regular expression
Question.
Write a regular expression for the languages:
all words in $\{a,b,c\}^{*}$ in which $a$ instance is followed by a sequence of at least two $c's$
The complement language of $1$
Attempt.
$\...
- 377
0
votes
0
answers
37
views
Regular language that specifies cycles of length 7 for rule 110
I found a language of which I may assume that it is regular, and now I want to know the grammar.
The words $w$ of the language have the form (A [0, 2, 4] B C+)+ ...
- 17.8k
-1
votes
1
answer
28
views
Symbol raised to the power of asterix raise to the power of asterix in regex [closed]
To describe the regex (a*+b+a)* in plain English you would simplify it to (a*)* + (b)* + (a)* . How would you describe (a*)* in English as the rest is just any number of bs or any number of as?
- 101
1
vote
1
answer
74
views
Pumping lemma for 0^f1^g2^g?
I am trying to prove that the language
$$\{0^g1^h2^j|h\ne j,g\ge2\}$$ is not regular. So far I have $x=0^m,y=0^f,z=0^{p-m-f}1^p2^{p+1}$. I don't know where to go from here, all of the examples I can ...
- 23
0
votes
0
answers
47
views
Is there a procedure to give a generating function for arbitrary regular languages?
The SchΓΌtzenberger methodology can enumerate the number of words of given length $k$ for unambiguous context free languages by a generating function. But not all regular languages are unambiguous ...
- 17.8k
0
votes
0
answers
38
views
pumping lemma: L1 = {a^n b^n : n β N} not regular
I am trying to prove that L1 = {a^n b^n: n β N} is not regular.
Proof: Assume L1 is regular. Let m be the number from the pumping lemma length p. Consider the string s = {a^m b^m } β L and |s| β₯ m. By ...
- 1
0
votes
1
answer
28
views
How to prove that for any $w_1,...,w_n \in \{0,1\}^*$ regular expression $w_1^*w_2^*\dots w_n^*$ doesn't represent language $\{0,1\}^*$?
How to prove that for any $w_1,...,w_n \in \{0,1\}^*$ regular expression $w_1^*w_2^*\dots w_n^*$ doesn't represent language $\{0,1\}^*$?
- 315
0
votes
0
answers
28
views
Finding an infinite regular language from the difference of two non-regular languages.
Next Tuesday I'll have to orally discuss a test that I did a few days ago with my Theoretical Computer Science professor. In the test, there was an exercise that I couldn't solve that stated:
Specify ...
0
votes
0
answers
43
views
Is b*a(a+b)* equivalent to (a+b)*a(a+b)*?
So two regular expressions are equivalent if they are associated, i.e., produce the same regular language, I am curious about this because it is clear that the language produced by $b*a(a+b)*$ is ...
- 41