Questions about properties of the class of regular languages and individual languages.
3
votes
1answer
41 views
Is the symmetric difference of a non regular language L and a finite language f non regular?
The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$.
Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
1
vote
1answer
35 views
Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages
How can I prove this identity of languages?
My aproach is the following:
Let A, B and C to be languages, and let x to be an arbitrary string.
(A ∪ B) ⇒ x ∈ A ∨ x ∈ B
How do you proceed?
0
votes
1answer
44 views
Define a grammar to emmulate chess rules
Is it possible to define a 《chess language》:
language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?
I looked online but I cannot find a ...
-1
votes
1answer
32 views
Prove {0^n OR 1^2n OR 2^3n | n >= 0} is not context free
How to prove using pumping lemma {0^n OR 1^2n OR 2^3n | n >= 0} is not context free
This isnt the same language as {0^n1^2n2^3n | n >= 0} as this language the numbers need to be in order.
1
vote
1answer
27 views
Contradiction in regularity of a language
Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = ...
-2
votes
2answers
79 views
Context free Grammar for this context free language
How can I create a context free grammar for the language $\{p^2q^mpr^nq^{2n+m}| m,n \ge 0\}$, where $\Sigma = \{p,q,r\}$?
2
votes
1answer
241 views
Determining if given languages are regular or recursively enumerable
I came across following problem:
Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
$L_1 =\{M|M$ accepts at most 2016 strings$\}$
$L_2=\{M|M$ accepts at least 2016 strings$\}$
...
2
votes
1answer
37 views
Is the language $a^nwa^n$ regular?
The given description of language is:
$\Sigma=\{a,b\}$ and $L=\{a^nwa^n:n\geq 1,w\in\Sigma^*\}$
I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can ...
0
votes
1answer
27 views
Generation regular languages by context free grammar
I came across problem asking whether given statement is true and false. The statement given was as follows:
Every Type-2 grammar can generate regular language.
I felt that Type-2 grammar means, ...
4
votes
2answers
72 views
Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular
We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can ...
0
votes
1answer
25 views
Number of strings accepted by this regular expression
This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices.
If a regular ...
0
votes
3answers
68 views
Concatenation of language to itself zero times
I was solving this question:
Which of the following statement(s) is/are false?
$L^0=\{\epsilon\}$
$|L^0|=0$
The answer given was None. That is, none of these statements are false and ...
1
vote
1answer
38 views
“Or” in regular expressions
I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.
One basic problem I wanted to solve was ...
1
vote
1answer
44 views
Understanding facts about regular languages, finite sets and subsets of regular languages
I am aware of following two facts related to two concepts: regular languages and finite sets:
Regular languages are not closed under subset and proper subset operations.
It is decidable ...
1
vote
1answer
26 views
Difference between regular language and context free language
What is nature of difference of regular language and context free language?
My guess is
RL - CFL = RL
CFL - RL = CFL
Am I correct with this?
0
votes
0answers
22 views
Conversion from automaton to left linear grammar
I stumble across this problem:
Give right linear grammar.
The solution given was simple:
$S\rightarrow bA$
$S\rightarrow aS$
$A\rightarrow \lambda$
$B\rightarrow bA$
$A\rightarrow aB$
Earlier ...
2
votes
1answer
63 views
Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:
Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$
does not contain null string, then $R = Q + RP$ has a ...
-1
votes
1answer
28 views
Regularity under set difference
Let L be a regular language.
Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$
How do I prove it is wrong?
6
votes
3answers
739 views
Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?
Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?
1
vote
1answer
18 views
Prove or disprove those languages are regular
in my practice for a test I came across this question:
prove or disprove that those languages are regular:
I succeeded proving that the second language is nonregular with homomorphism but i'm having ...
0
votes
0answers
55 views
Show that language is context-free
Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such ...
2
votes
1answer
30 views
Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?
(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.)
Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language?
This question ...
1
vote
0answers
12 views
Pseudo-random regex-searchable function
Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties:
$f$ is efficiently ...
1
vote
1answer
28 views
Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?
Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.
My proof:
Let $M = (\Sigma, Q, \delta, q_0, F)$ be an ...
8
votes
5answers
2k views
Finite state automata: final states
In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram.
But this seems to be a fundamentally ...
3
votes
1answer
178 views
This doesn't seem like a valid regular grammar; my instructor says it is
The following is a screenshot of a lecture slide from my programming language concepts course:
According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
1
vote
1answer
36 views
Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$
Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$
I need some tips how ...
2
votes
1answer
30 views
unambiguous equivalent grammar
There is a grammar G given:
S->XaX
X->aX|bX|eps
I just replied to the first question that was ...
1
vote
1answer
41 views
How to prove that a bounded pushdown automaton is regular?
I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain ...
0
votes
0answers
17 views
Regular grammar question [duplicate]
Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same.
I have ideas on how i would ...
1
vote
1answer
35 views
If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language?
Let $L = \{ a^{2^n} \mid n \ge 0 \}$, which is a non-regular language (no proof here). Let $M = (\Sigma,Q,\delta,z_0,F)$ be a DFA with $\Sigma = \{a\}$, $Q = \{z_0\}$, $\delta(z_0, a) = z_0$ and $F = \...
2
votes
1answer
55 views
Language of all words accepted by a TM by at most $t$ steps is regular
Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$
$L = \{ w \in \Sigma^* : w$ is accepted by $M$ by at most $t$ steps$\}$
I want to show that $L$ is regular.
My attempt:
I'm ...
0
votes
0answers
23 views
Show that the set $\{uv | u \in L \ and\ v \notin L\}$ is regular
The full question is:
Let $L$ be a regular language over $\{a, b, c\}$. Show that the set $\{uv\ |\ u \in L \ and\ v \notin L\}$ is regular
I have the following answer, but I'm not sure if it's ...
0
votes
0answers
33 views
When proof by induction on length string is not possible?
I found out an exercise where you have to prove the correctness of the following CFG:
Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and
$\: G: S\rightarrow 0S11 | 0S111| \epsilon$
claim: Every string $w ...
1
vote
2answers
25 views
Closure of context-free languages under regular quotient [duplicate]
Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that
$C / R = \{w| \exists x \in R: wx \in C\}$
is also a context-free language?
4
votes
1answer
481 views
Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular
I believe this statement to be true. And here's my reasoning:
Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
2
votes
1answer
36 views
Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?
If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪
(rs)*.
I think this is not true. And I believe this would always be true :
(r ∪ s)* = r* ∪ s*
I wanted to clarify this ...
4
votes
1answer
71 views
The equational theory of regular languages has no finite set of axioms for general alphabets
According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms.
Why does this imply that it has no finite set of ...
0
votes
0answers
18 views
Is there any algorithmic way to decide the equivalence classes in the nerode relation?
Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$
The Nerode relation $R_L$ says
$xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$
By looking at the language : I can conclude ...
2
votes
1answer
36 views
If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?
I am confused interpreting the statement of this question:
"If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?"
Should the symbol "|" (such as) be understood as ...
0
votes
0answers
16 views
Prove that every infinite regular language has an undecidable infinite subset [duplicate]
I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due ...
0
votes
0answers
16 views
Trouble coming up with an expression to describe a DFA [duplicate]
This is a DFA that describes a language over {a,b} that only accepts a string if the number of a's in the string is not divisible by 3. I'm having difficulty coming up with an expression for it, I'm ...
1
vote
1answer
66 views
Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results
I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment.
$\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$
$\text{Prove ...
3
votes
2answers
59 views
The language of non-extendable strings of a regular language is regular
I recently came across this question in my textbook.
$ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $
$ \text{Prove that the language is also ...
1
vote
1answer
63 views
Proving that a Language is non-Regular
Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular.
I was wondering if my intuition holds for proving this language as not regular:
Let $q = \max(i, j) - \min(i, j)$.
...
0
votes
1answer
28 views
Show that C(n) = {a^k | k is a multiple of n} is a regular language
I came across this question in an exam book and was unable to find a solution:
Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1.
I wasn't able to ...
1
vote
1answer
26 views
Proving that language is regular or not [duplicate]
How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not:
$\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$
I started with the ...
-1
votes
1answer
40 views
Prove or disprove whether L is regular by definiton [duplicate]
Assume L is regular language, define 𝐿1 = {𝑣𝑤: 𝑣 ∈ 𝐿,𝑤 ∉ 𝐿}, prove or dispute L1 regular or not ?
3
votes
2answers
38 views
variable exponent in expression of a formal language
Take a look at the following expression:
{(AnB)m|n>0,m>0}
Or, to put it simply: the words in the language, have repeating parts consisting of, some A's followed by a single B.
There are TWO school ...
1
vote
1answer
40 views
Prove that A is non-regular using K-Complexity Non regularity theorem
Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$
Given $A \...
