The regular-language tag has no wiki summary.
3
votes
1answer
166 views
Notation of cross entropy
I have a question regarding a notation that seems to be very usual.
For starters, cross entropy is defined by:
\begin{align}H(X, q) &= H(X) + D(p||q) \\
& =-\sum_x p(x)\log_2 q(x)\end{align}
...
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 ...
0
votes
1answer
52 views
Confusion related to context free grammar
If G is a context-free grammar such that it has the productions of the form
$$
X \rightarrow \alpha Y
,X \rightarrow \alpha
$$
How can I show that L(G) is a regular language
2
votes
0answers
30 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 ...
2
votes
0answers
164 views
Regular, Context-free, Recursive, Recursively Enumerable Language Relationships
I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable.
If I am given ...
1
vote
0answers
32 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\}$
...
1
vote
0answers
75 views
Isn't the set of all literature a regular language?
Let one piece of literature be one string. Let's define our alphabet to be sufficient to represent all literature (e.g. we may need a page-turn character, etc). So, since the collection of current ...
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 ...
0
votes
0answers
76 views
Is this language regular?
Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ?
Here L is not the set ...
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 ...
0
votes
0answers
35 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 ...
