# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

171 views

### Is this a regular language ? SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2}

Question: Define the following operation: SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2} Let L1 be any language, and L2 regular. Prove that SubString(L1, L2) is regular. Thoughts: I need to somehow ...
641 views

### There exists a regular language A such that for all languages B, A ∩ B is regular.

There exists a regular language A such that for all languages B, A ∩ B is regular. The above given statement is true but I couldn't make any proof or find any proof. It is an objective type ...
493 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} ...
577 views

### Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
26 views

### Determine whether a given language $L$ is regular , CFL or nither.

Let $$L=\left\{w\in\{a,b,c\}^{\ast}\Bigg\vert \exists \sigma_1,\sigma_2\in\{a,b,c\}\text{ s.t } \#_{\sigma_1}(w)\ne \#_{\sigma_2}(w)\right\}$$ Determine whether $L$ is regular, context free or ...
17 views

339 views

### Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
35 views

### comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
40 views

### A Recursively Defined Set of Strings

Describe the strings in the set $S$ of strings over the alphabet $\Sigma = \{a,b,c\}$ which are defined recursively by: (1) $a$ is in $S$, and (2) if $x$ is in $S$, then $ax$ is in S, $xb$ is in $S$ ...
992 views

### How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\}$

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\}$$ $E \to aEbS$ $S \to c$ I do not know where to go next, or even if this is right at all?
40 views

### Why can't this be a Regular Language?

Given $L$ - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$. How can I prove that $L$ is not a regular language?
16 views

### Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
30 views

418 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 ...
32 views

### DFA - Union operation: How to?

I'm currently looking at deterministic finite automata, and learning how to combine two DFAs using AND or OR. I think I understand how to construct the INTERSECTION (AND) of two DFAs, but I'm at a ...
28 views

### proving not regular with pumping lemma

Not quite sure if I understand pumping lemma correctly. so if i have this language and i like to show it is not regular: L={ $q^a w^be^c| a,b,c \in N, a+b=c$}. If L would be regular, than there ...
24 views

### Constructing DFA - Criteria / Multiple solutions

I'm currently studying for my logic exam, and looking into examples on DFA construction. Assume the alphabet is {a, b}, and the language to be constructed is defined as follows: ...
178 views

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?
24 views

### Merging of two DFAs

I have 3 languages L1, L2 and L3 with x$\in$L1, y$\in$L2, z$\in$L3 ; x=$a_{1}a_{2}a_{3}...a_{n}$, y=$b_{1}b_{2}b_{3}...b_{n}$ and c=$a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}...a_{n}b_{n}$. Words of L3 are ...
43 views

### Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\}$ above the alphabet $\Sigma = \{a,b\}$ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
41 views

### Difference of a regular language and a context-free language

I know that given the context-free language L and the regular language R, the language L \ R is context free. But what about R \ L ? My attempt is as follows: R \ L = R $\cap$ $\overline{L}$ We ...
35 views

### Show that $L = \{a^p b^q \mid p, q \in \mathbb{N}^0 \setminus \mathbb{P}\}$ is not regular

Full disclosure: this is a homework question, so I'm only looking for a kick in the right direction. The original question notes that $\{a^p \mid \ p \in \mathbb{P}\}$ is not regular and that the ...
31 views

### relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
38 views

### Infinite recursive languages and infinite regular languages.

Could the following statement be correct? "Every infinite recursive language has as a subset an infinite regular language."
36 views

### NFA to DFA for odd a's and even b's

The regular expression for accepting odd a's and even b's I calculated is: (aa)*a(bb)* and the NFA: ...
49 views

### Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
77 views

### Pumping Lemma - non regular

Can everyone help me to show that: the language $$L = \{a,b\}^* \setminus \{a^m b^{2m} a^n\mid m,n \ge 0\}$$ is not regular. I don't know what is the meaning for the proof.
44 views

### Where did I go wrong creating a Deterministic finite automaton?

My goal was to create a Deterministic finite automaton that handled the regular language (00010 + 1101 + 1010)* and had a parity bit at the end to make sure 0's where even. To clarify what I mean by ...
30 views

### Finding a Regular Grammar

so I have to find a regular grammar to generate the following sets: $(1)$ $\{aa, ab, ac\}$ $(2)$ $\{ab^n,ba^n\mid n\ge 0\}$ $(3)$ $\{ab^{2n}\mid n\ge0\}$ I'm wondering if anyone can check my ...