The regular-language tag has no wiki summary.
2
votes
0answers
28 views
Pumping lemma for $a^nb^{2n+1}$
I know how to solve pumping lemma for $a^nb^n:n\geq 0$.
But I don't understand how can I solve this example : $a^nb^{2n+1}:n\geq 0$.
I tried to solve it but I am not sure that I have solved it ...
0
votes
2answers
34 views
Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.
Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.
It seems to use one Lemma: Pumping Lemma.
1
vote
2answers
40 views
Are regular languages necessarily deterministic context-free languages?
The original problem
Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers.
a) Is M-N necessarily context-free?
...
2
votes
1answer
16 views
If $\{w^k|w\in L\}$ regular implies L regular?
If L is a language and the language
$$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$
is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence)
We came across this question when ...
1
vote
2answers
25 views
Proving irregularity of a language
While learning about formal languages, I found the following problem:
Let us consider words over the alphabet $\lbrace 0, 1\rbrace ^3$. We say that a word $\langle a_1, b_1, c_1 \rangle \ldots ...
0
votes
1answer
29 views
Algorithm for checking if regular language has given property
Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property:
$$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq ...
1
vote
0answers
29 views
Proving that language is regular or not regular
Let $L$ be a regular language. Prove that:
$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$
$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$
...
3
votes
2answers
86 views
Is $\frac12 L$ a regular language?
Let $L$ be a regular language. Is $\frac{1}{2}L := \left\{ w: \exists_u |u|=|w| \wedge wu\in L \right\}$ regular too?
I think the answer is YES. But I don't know how to prove it. I was trying to ...
1
vote
1answer
50 views
Is language of binary representations regular?
Let $bin(n)$ denote binary representation of an integer $n$. Let $L=\left\{bin(n^2):n\in\mathbb{N}\right\}$. Is $L$ a regular language?
1
vote
1answer
41 views
How to prove that given language is not regular?
Prove that
$$L=\left\{uvvw\mid u,v,w \in \{a,b,c\}^*\text{ and }v\ne\varepsilon\right\}$$
is not regular a regular language.
0
votes
0answers
14 views
Shortest trace for LTL
Given a finite trace semantics for LTL (one where u,i |= X phi does not hold if i = |u|) is there a better bound of the length of a minimal trace for a satisfiable formula ?
By better, I mean better ...
1
vote
2answers
78 views
Infinite union of finite unions
Is the following sound reasoning, and if so, why?
Letting $S$ be a language over the alphabet $\Sigma$,
$$
\bigcup_{i=0}^{\infty}\left(\bigcup_{k=0}^{i-1}S^k\right) = \bigcup_{i=0}^{\infty}S^i
$$
0
votes
0answers
33 views
Chomsky Normal Form solution for a problem
Here is my attempt at CNF,
Original:
$$
\begin{align*}
S &\to 1 A \mid O B \\
A &\to O B O \mid 1 0 \mid \epsilon \\
B &\to A 1 A \mid 0 1
\end{align*}
$$
CNF:
$$
\begin{align*}
S ...
2
votes
2answers
49 views
Giving a regular grammar for the language
I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
2
votes
1answer
73 views
Pumping Lemma problem
Apply pumping lemma to each of these and prove that they are not regular.
$L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$
$L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$
Here my ...
0
votes
1answer
39 views
Interesting problem on finding a Regular Expression for a language
Lets say we have some language P such that P = {z^n } where n is not divisible by 10.
Give a regular expression for this language and then a generalized regular expression thats shorter than the ...
2
votes
1answer
71 views
Is there a problem with this example?
In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
3
votes
1answer
58 views
Does the Halting Problem apply when evaluating programs that are regular languages?
Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
1
vote
1answer
97 views
If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular
Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language.
I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
2
votes
2answers
76 views
Is this proof using the pumping lemma correct?
I have this proof and it goes like this:
We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$.
Then, the following proof is given:
There is a $p$ ...
1
vote
1answer
87 views
Regular Languages Algorithm?
I need help proving the following question:
Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length.
So far, I know ...
1
vote
1answer
83 views
Prove that if $ L $ is a regular language over the alphabet $ Z = \{ 0,1 \} $, then $ L' = \{ax \mid x \in L \} $ is also regular for any a in $Z$.
Prove that if $L$ is a regular language over the alphabet $Z = \{0,1\}$, then $L' = \{ax \mid x \in L\}$ is also regular for any $a \in Z$.
I'm not sure how to even begin on this one. If even a ...
3
votes
2answers
43 views
If $L\in REG$ then $M$ has a finite number of distinct rows
Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$:
$$
m_{x,y}=\begin{cases}
1 & x y\in L\\
0 ...
2
votes
1answer
61 views
Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?
Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?
0
votes
1answer
72 views
The regularity of Markov chains with a threshold
I am studying Paz's "Introduction to Probabilistic Automata", and there is an exercise I cannot solve:
Ex. 11, p. 170: Prove that the number of nonregular events of the form $\{x \mid p^A(x) > ...
1
vote
1answer
88 views
How would I go about proving for this NFA?
I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following:
N accepts the string x if the number of distinct ...
1
vote
2answers
39 views
Regular languages question
Describe these languages over $\Sigma={a,b}$
$\Sigma^{*}(a\cup\epsilon)b^*$
$a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^{*}a\Sigma$
Just making sure I understand some basic concepts...
First one ...
3
votes
2answers
187 views
Question about regular languages and finite automata
We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
2
votes
2answers
78 views
Basic regular expressions problem
I'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular ...
1
vote
2answers
50 views
Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?
DFA
Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$?
For part 2, wouldn't it require M states if the word length is M?
1
vote
2answers
119 views
suffix regular language
Can someone give me an idea how to prove this:
suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...
1
vote
2answers
77 views
How to prove that the following language is not regular?
This is the following problem that I've been having difficulty on:
For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the ...
1
vote
2answers
55 views
Proving this language is regular?
Is $$L =\big\{x^ny^m : |n-m| = 2\big\}$$ a regular language?
I can't seem to figure this question out, and i've tried drawing a dfa but I still can't seem to find it. If there is a possible dfa, ...
1
vote
2answers
37 views
Proving a language to be regular
Let $\Sigma_{2}={ \begin{bmatrix} 0\\ 0 \end{bmatrix},
\begin{bmatrix} 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1
\end{bmatrix},\begin{bmatrix} 1\\ 1 \end{bmatrix}}$
...
1
vote
3answers
62 views
regular language?
I need help proving whether this language is regular or not.
$$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$
That is, the number of $a$'s is even and the ...
1
vote
1answer
56 views
Question about infinite union of non-regular languages
If none of the languages $L_1$,$L_2$,... is regular,
and $L_i \subseteq L_{i+1}$ for each i, is $\bigcup_{n=1}^\infty L_i$ regular?
I guess the answer is no for any given languages, but I cannot ...
2
votes
1answer
349 views
Converting to Chomsky Normal Form
I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
2answers
78 views
How can I prove the majority of three languages is also regular if the three languages are regular?
This is a question I've been stuck on recently:
Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
0
votes
2answers
54 views
What are the states of this NFA?
I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states:
$q_0$: the string ends with bb.
...
1
vote
1answer
69 views
Proving this language is not regular
Let
$$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$
I have been trying to get a start on this proof for a long time now with no success. What would ...
2
votes
2answers
158 views
Pumping Lemma Excercise
I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ...
2
votes
1answer
123 views
Proving a language is regular or irregular
I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to ...
4
votes
2answers
101 views
Pumping Lemma proofs
I am having a hard time writing a Pumping Lemma contradictory proof for the below statements.
1) $L_1 = \{ ww \mid w \in E^* \}$ <--- I don't understand how to read this. This is what I tried: ...
0
votes
2answers
103 views
Determine if a language is regular from the first sight
Is there a way to guess if a language is regular from the first sight? I.e. in order to choose proof methods, I have to have some hypothesis at first. Do you know any hints/patterns?
I need this to ...
2
votes
1answer
27 views
Regularity of “middles” of words from regular language
I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other ...
1
vote
2answers
284 views
How to prove by pumping lemma these languages are not regular?
$L_1 = (a^k * b^r \mid k \neq r^2)$
$L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
0
votes
1answer
73 views
Building a regular grammar from NFA
I'm requested to make a regular grammar from a given NFA.
In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same ...
1
vote
1answer
57 views
Proving or disproving regularity of a language
The question is as follows:
If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular
My intuition says that it's wrong so I've been looking for a ...
0
votes
2answers
76 views
following languages regular or not?
Please help me determine if those languages are regular or not. If not, I'll be glad to get a direction to prove it by contraditiction of the pumping lemma:
$L = \{a^n\mathord{*} a^m \mid m \equiv ...
0
votes
1answer
34 views
proving by construction that language is regular
I had this exercise saying the following:
$$
L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\}
$$
I need to prove that $L$ is regular by defining an ...
