Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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 \...