# Tagged Questions

Questions about properties of the class of regular languages and individual languages.

34 views

### Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)?

Given a DFA (D1) with P1 states, that accepts a language L1. Modify (D1) to create another DFA (D2), such that it will accept the language L2 that is defined as: All strings in L1 that are also a ...
32 views

### Why L = L^2 for the non-regular language L = {a^nba^n | n=>0}*?

I can't seem to understand why does L=L^2 for: L = {a^nba^n | n=>0}* Thanks!
16 views

### Prove that half(L) is also regular if L is a regular language [duplicate]

Given a regular language $L \subseteq \sum^*$ prove that the language $half(L) = \{w \space | \space ww \space \in \space L \}$ is also a regular language. -- Please give a hint or two. Have ...
40 views

31 views

### Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
40 views

### The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
78 views

### Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
23 views

### Can an (extended) regular grammar have multiple nonterminals in its RHS?

Standard (right) regular grammars have three kinds of rules: A <- "" A <- "a" A <- "a" B This is OK for a theoretical point of view, but a big ...
42 views

### Context free Grammar and regular set

I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in ...
25 views

### Right linear grammar special case

According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$, does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$...
43 views

44 views

### What's the difference between the concatenation and union of symbols within a language

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression (a + b)* (abba* + (ab)*ba) Can ...
85 views

### Show language is not regular

Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma: $$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$ \text{...
71 views

### Show L1 /L2 is regular [duplicate]

Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. The quotient of $L_1$ and $L_2$ is the language $L_1/L_2 = \{x : \exists y \in L_2, xy \in L_1\}$ Show that if $L_1$ is regular ...
118 views

40 views

### How do I show that an equivalence class of a language containing an empty string is infinite

The question is as follows: Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not \$\{ \epsilon ...
893 views

### Can we make a non-regular language regular via concatentation?

My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?