# Tag Info

## Hot answers tagged formal-languages

3

I think you are conflating syntax and semantics. A formal language is RE if it is possible to recursively enumerate all valid "sentences" (read "complete programs"). Validity here effectively means only that a compiler could convert the program into an executable, without saying anything about what that executable does. That has basically nothing to do ...

3

An alphabet is a set of symbols, therefore if your you treat $\{a,b,c\}$ as a single symbol, it is a valid alphabet.

2

Your language is not context-free. You can see this by applying the inverse of the homomorphism which sends $a$ to $a$, $b$ to $bb$ and $c$ to $cc$; this results in the language $\{a^ib^ic^i : i > 1\}$, which differs from a well-known non-context-free language by just a finite number of words.

2

Let $L$ be a context-free but not regular language over $\{0,1\}$ such that its complement language $\overline L$ is also context-free. Then $\overline L$ is not regular and $L\cup\overline L=\Sigma^*$ is regular. In particular, let $L=\{a^nb^n\mid n\in\Bbb N\}$. The previous example requires you to verify that both $L$ and $\overline L$ are context-free. ...

2

Let us prove a more general result: For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular. The language we construct will be unary, that is, of the form $L = \{a^n : n \in S\}$, where $S \subseteq \mathbb{N}$ is $$S = \{ km : k \geq 0 \} \cup \{ m^k + 1 : k \geq 1 \}.$$ Let $1 \leq p \leq m-1$,...

2

There's is a significant difference between "arbitrarily long" and "infinite". As a simple example, an integer can have an arbitrarily great magnitude; formally, for every integer, there exists a larger integer (its successor), which in turn has a successor, and so on. But all integers are finite; $\omega \notin \mathbb{N}$. (Or, if you prefer, $\infty \... 2 Consider, for instance,$A = \{ \varepsilon \}$. Then$X = AX$, so$X = AX \cup B$holds for any$X$with$B \subseteq X$. 2 The complement (note spelling) of$\mathrm{SAT}$is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all. In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, ... 1 Unless you must deal with unary regular languages, there is no need for complex math ... Just pick an irregular language that is able to "capture and mask" the concatenation of itself; e.g. over$\Sigma = \{a,b \}L = \{ (a^ib^j) (a^n b^n) \mid i, j \geq 1, n \geq 1\} \; \cup \;  \{ (a^ib^j)^k \mid i, j \geq 1, k \neq 2\}LLLL$is equal to .... 1 Let us view the programming language abstractly as the (finite) description of a Turing machine's operation, which I assume is what you are aiming at by saying the language is RE or context-sensitive. The setting here is us having a single machine (a "universal" interpreter) to which we feed inputs of the form$(P, x)$where$P$is a program,$x$is an input ... 1 If we have a word,$w=a_1a_2\dots a_n$where the$a_i$are characters from the underlying alphabet, then the prefixes of$w$are the empty word,$\epsilon$, and the words$a_1$,$a_1a_2$,$a_1a_2a_3$, ...,$a_1a_2\dots a_{n-1}a_n$. In informal terms, the prefixes of a word consist of all left-hand segments of the word. 1 There are three standard regular expression operators: concatenation, alternation, and Kleene closure. (Note that we're talking about regular expressions in the formal mathematical sense, not the random collections of hacks which comprise typical regex libraries.) These can be thought of as operators on (possibly infinite sets); alternation is set union, ... 1 As I understand it, you are interpreting the space$\{ 0,1 \}^\ast$to be the (disjoint) union of$F$and$\overline{F}$, where$F$is the set of valid formulas and$\overline{F}$is the set of strings which do not encode a formula (according to some unspecified encoding). Then, in your perspective, we should have that$F = \textsf{SAT} \cup \overline{\...

1

In typical usage of the pumping lemma, you assume that the word you chose for pumping is written as $w=xyz$, with $x,y,z$ satisfying the conditions of the pumping lemma. Then, in most cases, you reach a contradiction by saying that e.g., $xy^2z$ is not in the language. This is "pumping up", since you "add" copies of $y$. In this case, however, you reach a ...

1

Your question doesn't make sense because of a category error. "Regular" is a property of sets of strings. A set of languages is a set of sets of strings, so it doesn't make sense to ask if it's regular.

Only top voted, non community-wiki answers of a minimum length are eligible