Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
0
votes
1answer
37 views
Let u and v be two strings. What about the reverse order of their concatenaited string?
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?
Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
3
votes
2answers
92 views
Why is every finite language A ⊆ Σ* regular
So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can ...
4
votes
2answers
49 views
Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?
I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
0
votes
0answers
38 views
Prove or Disprove: If A is regular and A ∪ B is not regular, then B is not regular
I'm doing a problem where I need to prove the following statement:
If A is regular and A ∪ B is not regular, then B is not regular.
In another similar problem that I did, I know that if A is regular ...
2
votes
1answer
38 views
Union of infinitely many regular languages [duplicate]
I need to prove or disprove the following statement.
If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.
I know that if two languages ...
-5
votes
0answers
19 views
Should we still study finite automatan? [duplicate]
Can anybody help me with this homework question?
In the era of information, technology changes at drastic speed, and the same is observed in Computer Science and Information Technology. The need ...
0
votes
1answer
63 views
Proving the singleton language {x} is regular for all x ∈ Σ*
So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
1
vote
1answer
28 views
Pumping Lemma vs Myhill-Nerode [duplicate]
I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.
Let us take the following as an example:
$$ L = \{ a^n b^n \mid n \ge 0\} $$
...
0
votes
0answers
26 views
Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]
Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved?
Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
1
vote
1answer
26 views
Pumping Lemma on Language with subtracted length
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given
$$ L = \{ a^k b a^{m-...
0
votes
0answers
12 views
How to find equivalence classes for a regular language? [duplicate]
I was wondering if there is a formal approach to find equivalence classes for a regular language.
My guess:
Construct a minimal DFA based on given regular language.
Based on states in DFA, we can ...
0
votes
1answer
22 views
$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
I think this languages is regular. I write regular expression:
$(1 + 2 + 0) ^ {*} (11 + ...
0
votes
1answer
41 views
Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$
In my opinion complement of the L language is
$L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$
I choose to ...
3
votes
2answers
42 views
First half of context-free palindromes
If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.
Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
0
votes
1answer
44 views
Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither
$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $
Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-...
1
vote
2answers
68 views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
64 views
Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $
I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
-3
votes
0answers
26 views
In what complexity class is the problem of checking whether two NFA states are equivalent? [closed]
That is, check if two NFA states accept the same language?
0
votes
1answer
85 views
Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's
The following question on the theory of computation is GATE 2019 CS question 24:
For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
3
votes
2answers
27 views
What's the true meaning of $(a + b)^\omega$ in regular expression
I'm starting to dabble in language theory, regular expression & infinite words.
I'm not quite sure I completely get the meaning of this expression:
$(a + b)^\omega$
$^w$ meaning infinite ...
0
votes
2answers
29 views
Is a language that sits between two regular languages also regular?
Suppose that L0, L1, L2 are languages over the same alphabet and that
L0 ⊆ L1 ⊆ L2.
Is it true that if L0 and L2 are regular, then L1 must be regular as well?
...
1
vote
1answer
48 views
How I can find all equivalence classes by Myhill-Nerode?
first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest.
The topic is Myhill-Nerode ...
0
votes
1answer
36 views
Maximum number of words in deterministic finished automata with k-states [closed]
I have exercise:
We have a given finished deterministic automata. It has 5 states and is
based on the alphabet {a, b, c}. It can create n different words (we assume that n <
inf). What maximum ...
1
vote
1answer
26 views
Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?
The definition says that language has prefix/suffix property requires that there is no code word in the ...
0
votes
1answer
36 views
operate infinite times over a regular language
Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$.
Is it possible to prove $T^∞(L)$ is regular?
$T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$...
2
votes
1answer
55 views
Density of regular language containing all squares
I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.
Suppose we ...
0
votes
1answer
33 views
How can I find the Myhill-Nerode classes for the language A?
I have the following task (no homework).
Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$...
1
vote
1answer
15 views
Infinite sequence has $m$ consecutive digits – regular languages
Suppose we have an infinite sequence over the decimal alphabet, call it $w$. For $k\in \{0,1,2,3,4,5,6,7,8,9\}$, let $L_k = \{m\geq 0: \text{$w$ contains a run of $m$ $k$'s}\}$ be a language. Here a ...
2
votes
2answers
43 views
Myhill-Nerode equivalence classes of $\{1^n0^n\}$
I have the following task and its solution.
Question
Given the language
$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$
...
1
vote
2answers
44 views
Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n
The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
1
vote
1answer
35 views
How to build a finite automaton for right quotient of a regular language?
Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$.
Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$.
Let $M$ be a finite ...
1
vote
1answer
38 views
Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?
Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\...
1
vote
1answer
32 views
How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?
Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular:
$$
G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } ...
1
vote
1answer
35 views
How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
I think this could be a good exercise and the conditions are ...
0
votes
0answers
19 views
What is “Phrase structure grammar”?
I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar:
Type-0 grammars generate recursively enumerable languages. The
...
1
vote
1answer
56 views
proof of the rice's theorem
Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof:(This is from sipser'...
2
votes
1answer
31 views
How to choose a word to apply the Pumping Lemma?
I have some questions about the PUMPING LEMMA.
First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes.
And sorry about my English :)
...
1
vote
1answer
57 views
Induction on strings (words)
Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word.
$quer : \Sigma^*\to \Bbb N$ with:
$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\
...
2
votes
0answers
37 views
If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]
How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
1
vote
1answer
62 views
Which word could I use for the pumping lemma?
I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma.
Task:
Be
$\sum { =\left\{ a,b,c \right\} } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \...
2
votes
1answer
50 views
How to prove a language is not regular using the Pumping Lemma?
I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.
Task:
Prove that $M = \left\{ a^...
1
vote
1answer
31 views
is $0^x1^y$ context-free?
given that L is regular, does the following make a context-free language?:
i) $\{0^x1^y \mid 0^{x+y} \in L\}$
ii) $\{0^x1^y \mid 0^{x-y} \in L\}$
since L is regular, i presumed that i) can be put ...
0
votes
2answers
32 views
Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?
My book states that the language
$$L_1 = \{a^nb^n\mid n\geq 1\}$$
is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really ...
1
vote
1answer
21 views
Can Non-Linear Grammars generate Regular Language?
I stumbled upon the following non-linear grammar
$$S \to AB$$
$$A\to aaA\mid \epsilon$$
$$B \to Bb\mid \epsilon$$
and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} ...
0
votes
0answers
21 views
How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]
I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
0
votes
1answer
50 views
Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
5
votes
2answers
228 views
Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.
I saw the answers to this question: are regular languages closed under division
and the proof sketch is not ...
1
vote
2answers
35 views
Does this DFA describe this regular expression?
For the expression (ab)*ba I came up with the following (very poorly drawn):
However, this was not the correct answer - apparently the solution requires five ...
0
votes
1answer
54 views
picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}
If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$
when i pick a word for the language, would it be correct if i pick any of
these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^...
2
votes
2answers
55 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
