Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,574 questions
Filter by
Sorted by
Tagged with
82 views

Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?

I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are ...
23 views

Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin

I'm currently reading a paper on First-order definable languages by Volker Diekert and Paul Gastin. Im having trouble understanding a part of the proof for lemma 3.2 (splitting lemma). The part I'm ...
119 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
25 views

Words which, cyclically shifted twice, equal their reverse

Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ ...
107 views

73 views

Proving that $\{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

I have a question about the pumping lemma for context-free languages. I understand the conditions of the pumping lemma. Assume $L$ is context-free. Let $n>0$ be the pumping length given by the ...
40 views

A question about domains in Karp reductions

A basic question or request for clarification regarding Karp reducibility: Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote ...
35 views

Formal Grammar: derivation form posted on Wiki?

Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step". I have a question on the condition when there are multiple productions for a single non-...
19 views

generating strings from this formal grammar [duplicate]

Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
123 views

Prove that $(L^R)^* = (L^*)^R$

Prove that $(L^R)^* = (L^*)^R$ for all languages $L$. My attempt: Suppose $w \in (L^R)^*$. So, $w = w_1\dots w_l$, for some $w_1, \dots , w_l \in L^R$. Since $w^R \in L$, then $w^R = w_l\dots w_1$, ...
205 views

Show that $L$ and $\overline L$ cannot be both finite

Let $L$ be any language on a nonempty alphabet. Show that $L$ and $\overline L$ cannot be both finite. This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" ...
Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$
Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$. This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. ...