Tagged Questions
0
votes
0answers
30 views
Is the language regular? [duplicate]
A is a finite alphabet set, $a∈A$. Given $n∈Z$, is the language $ L=\{(a^n,a)\}^∗$ over $\{A∪\{\$\}\}\times \{A∪\{\$\}\}\\{}$\{(\$,$)} regular ?
Here L is not the set $ \{a^n,a\}^∗$. L is not a ...
0
votes
0answers
28 views
Is this language $L=\{(a^m,a)\}^∗$ regular?
Given $m∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a)\}^∗$ is subset of $A^*\times A^*$. Is this language regular ? why or why not ?
Here L is not the set $\{a^m,a\}^∗$. L is not a unitary set ...
2
votes
1answer
24 views
Regular composition of non-regular language
I've got the following problem:
Let's take language $L$.
Is it posible that $L$ is not regular itself,
but it's composition $L\cdot L$ becomes regular?
I suspect that's correct, yet I ...
0
votes
1answer
45 views
Give a regular grammar for L
Give a regular grammar for L= {a^n b^n : n<=100}
I would do something like this :
S---> A | empty string
A---> aB| empty String
B---> Ab
but How do we keep count of the number in the grammar? ...
0
votes
2answers
38 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.
0
votes
0answers
15 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 ...
2
votes
2answers
57 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
72 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 ...
1
vote
1answer
100 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
78 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
93 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 ...
3
votes
2answers
46 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 ...
1
vote
1answer
89 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 ...
3
votes
2answers
209 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 ...
1
vote
2answers
52 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
146 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
56 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
3answers
63 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 ...
0
votes
2answers
55 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
2answers
292 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 )$
1
vote
2answers
140 views
Showing that a language is regular - Pushdown Automaton
So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.
0
votes
3answers
79 views
showing that a regular language is regular after taking a letter off or after adding letters
I'll be happy to recieve help with this one:
Given the regular language $L$ defined over alphabet $\{a,b\}$, show that the following languages are also regular:
$\{xy\mid xay\in L\}$ ...
0
votes
1answer
228 views
Formal proof of the concatenation of two regular languages automaton
During an exercise for college, given two NFA's, $A_1\text{ and }A_2$ that accept the languages $L_1\text{ and }L_2$, I've built a NFA, $M$ that accepts the language $L_1*L_2$ (concatenation).
The ...
2
votes
1answer
47 views
Is regularity is preserved under reversal?
When talking about languages and regular languages.
Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar.
Therefore, the ...
0
votes
0answers
45 views
Show that $\{ a^p \mid p\text{ is prime} \}$ is not regular [duplicate]
Possible Duplicate:
Why isn’t this a regular language?
Show that $\{ a^p \mid p\text{ is prime} \}$ is not regular.
The definition is: a language $L$ is called "regular" if there exists ...
4
votes
3answers
132 views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
6
votes
1answer
84 views
Existence of NFA for this language
I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
3
votes
2answers
95 views
Showing $L=\{uw \mid \exists v:uv\in L_{1},vw\in L_{2}\}$ is regular
Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$.
I wish to prove that $L$ is regular using only closure properties
(such as ...
1
vote
1answer
222 views
A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$
The following is an exercise in a book I am reading:
Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words
over $\Sigma$ that do not contain $ab$ as a sub-word.
Find a regular ...
0
votes
1answer
57 views
Regular expression arithmetics
What are the rules of regular expression arithmetics ?
For example: Let $\Sigma=\{0,1\}$
$1. 1+01=(\epsilon+0)1$.
$2. (\epsilon+00)^*=(00)^*$
2
votes
1answer
106 views
Is the set of codes of Deterministic Finite-State Automata a regular language?
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
0
votes
3answers
163 views
Different version of pumping lemma and how to prove it
I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs.
Consider the following version of pumping lemma.
For any ...
2
votes
2answers
215 views
The language that contains no proper prefixes of all words of a regular language is regular
Let $L$ be a regular language. I need to prove that the language
$$M_L = \{w \in L \; | \forall x \in L \; \forall y \in \Sigma^+ : w \neq xy \}$$
that contains all words of L that do not have a ...
2
votes
4answers
2k views
Intersection of two deterministic finite automata?
I'm trying to solve a problem where I have to create a DFA for the intersection of two languages.
These are:
$$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
2
votes
1answer
171 views
Constructing finite state automata corresponding to regular expressions. Are my solutions correct?
I have drawn my answers in paint, are they correct?
(4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions:
(i) 0
My Answer 4ci
(ii) ...
2
votes
3answers
108 views
Regular Language
Prove that the language $\{a^{k} \mid k \equiv 0 \text{ or }k\equiv 2 \pmod 5\}$ is a regular language. I am just trying to figure this problem out for my own benefit. I am new to learning this ...
