Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
0answers
43 views

What are the technical reasons for which the empty string is not allowed to be accepted by a Turing machine?

Below are the excerpts from the automata text by Peter Linz. Definition 9.3 Let $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ be a Turing machine. Then the language accepted by $M$ is $$L(M) = \{ w \...
3
votes
0answers
37 views

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

$\text{Consider the language $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ }$ $\text{and the following statements.}$ $\quad\quad\text{I. $L$ is deterministic context-free.}$ $\quad\quad\text{II. $L$...
1
vote
1answer
45 views

Would a parser for this left-recursive grammar require infinite input?

I am considering this left recursive language grammar production rule: Expr = Expr, "a" ; As a production rule, I believe that this can be used to ...
-1
votes
1answer
52 views

Is this language a context free language?

Consider the following language, where the alphabet is $\{0, 1, 2\}$: $B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$. Is this language a context free language? Prove your answer. I am ...
3
votes
3answers
42 views

Star notation for context-free language alphabet?

I noticed that some "design-the-grammar" problems say verbally Alphabet is $\mathbf{\{0,1\}}$. $\{w \mid w \text{ contains at least three 1s}\}$ and some problems list it as $\{ w ∈ \...
3
votes
2answers
497 views

Given L is a regular language, prove that Perm(L) is Context-Free

Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the ...
1
vote
1answer
50 views

Exclusion in a context-free language?

I am learning automata theory, and I am confused about this exercise: Give context free grammar to create the following language where the input alphabet is $\{a,b\}$ $L = \{w \text{ where }w\text{ ...
1
vote
1answer
31 views

Proving a language with $(ab)^n$ is not regular with pumping lemma?

I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular: \begin{align} L_1 &= \{(ab)^n c^m \mid n\ge 1, m\ge 2n \} \\ L_2 &...
1
vote
0answers
49 views

Why H-trivial monoids correspond to the variety of aperiodic monoids

I have two similar questions, one about the H-trivial monoids and one about the R-trivial monoids. I cannot see the reason why H-trivial monoids, i.e., the monoids where H induced classes are ...
2
votes
1answer
61 views

Is $\{\varepsilon\}$ a conventional way to mark the empty language?

I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer ...
3
votes
2answers
36 views

Language equivalency for modified CFG closed over intersection

Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both ...
1
vote
0answers
34 views

Determining whether a language $L_{a}$ is recursively enumerable

I'm trying to determine whether a language $L_{a}$ is recursively enumerable, but first I'm having trouble deciphering the definition $L_{a}$ given the following question: Given an recursively ...
3
votes
1answer
52 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 ...
0
votes
1answer
20 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 ...
2
votes
1answer
116 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
0
votes
1answer
22 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$ ...
2
votes
0answers
51 views

Regular expression vs rational expression

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$. Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows: $|L| ...
1
vote
1answer
50 views

Regular language where syntactic right congruence and syntactic congruence differ

Find an example of a regular language where the syntactic right congruence and the syntactic congruence are not identical. I have gone through the relevant definitions and understand them, but could ...
1
vote
1answer
69 views

If we say L ⊂ {a, b, c}* then is L an infinite language?

I wonder if we say L ⊂ {a, b, c}* then is L an infinite language? I think Kleene star makes me think L is an infinite language.
1
vote
1answer
105 views

Constructing a context-free grammar

I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, ...
0
votes
1answer
32 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
-3
votes
2answers
64 views

Prove that the language Cats-Vs-Dogs is undecidable

Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...
0
votes
0answers
23 views

Formal languages. What is the definition of $L^*L^*$? [duplicate]

I need to use it to prove $L^*=L^*L^*$. So I know that $L^*=L^1 \cup L^2 \cup L^3\cup\ldots$ But how do you describe $L^* L^*$?
0
votes
1answer
29 views

Regular set of the “does not contain” kind

Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses $L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$? Well, the part ...
1
vote
1answer
189 views

How to prove the language of contractible strings is context-free but not regular?

How to prove this language is context-free but not regular? I can't figure out it. A string is contractible if there is a sequence of contractions which result in the empty string, where a ...
1
vote
2answers
45 views

Pumping lemma for regular languages. Proof

Please help me understand the following $L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ To prove: The language $L$ has regular pumping ...
1
vote
2answers
65 views

Understanding the language

Could you please help me understand the following Language $L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ what does $a_i = a_{i+1}$ mean? ...
0
votes
2answers
61 views

How to prove that $L^* = L^*L^*$

I need to prove or disprove that $L^* = L^*L^*$. Intuitively, I know this is true, and I know I need to prove that $L^*$ is subset of $L^*L^*$ and that $L^*L^*$ is a subset of $L^*$. But I am really ...
1
vote
1answer
52 views

Regular languages closed under prefix operation

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$ ...
0
votes
0answers
16 views

L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]

I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it. Can someone suggest a grammar for this?
0
votes
1answer
49 views

Which of the following words is in the language of the grammar G?

This is taken from a practice quiz by my university. I ruled out that aabbbaab is not part of the grammar: S → aSb → aaSbb... This shows that I can't make this word because it would have to have ...
0
votes
1answer
56 views

Pumping Lemma Proof (Type of wcw language)

I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma. The structure of the language i think can be explained ...
1
vote
2answers
33 views

How to evaluate a Kleene's Closure through CFG and attribute grammars

For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce. For T = {a, b,*,(,)} and an arbitrary ...
0
votes
1answer
45 views

How can I make the following grammar unambiguous

Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y My attempt: ...
0
votes
2answers
56 views

Cardinality of sets and strings -> confused

I have a question regarding the cardinality of sets and strings. If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted. If $ \Sigma^+ $ is empty, the ...
3
votes
0answers
54 views

Words of the same length in a language

Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$. I am wondering if there is some good terminology for $L\cap\Sigma^n$. Of course I could say "the set of ...
2
votes
1answer
30 views

Show that moving one symbol to the end still makes a regular language

Question For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^*$), $\texttt{MOVE}(\sigma)=wa$ This is ...
-1
votes
1answer
65 views

For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$

The $\Leftarrow$ direction is straightforward. On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it. For NTM, Non Deterministic Turing Machine, $M$, for ...
0
votes
1answer
26 views

Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$

When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa. I'm thinking that this equal to $P=NP$, but I saw a solution (...
0
votes
2answers
51 views

Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular

So I have the question: show "Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get. They all take: $\bar{L}∩(...
1
vote
1answer
57 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 ...
1
vote
1answer
35 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 ...
0
votes
1answer
26 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-...
0
votes
0answers
18 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 ...
1
vote
1answer
39 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$, ...
1
vote
2answers
45 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" ...
0
votes
1answer
51 views

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. ...
1
vote
1answer
43 views

Prove that $(uv)^R = v^Ru^R$

The reverse of a string, introduced informally above, can be defined more precisely by the recursive rules $$a^R=a,$$ $$(wa)^R=aw^R,$$ for all $a \in \Sigma$, $w \in \Sigma^*$. Use this to prove that $...
2
votes
2answers
81 views

Why can't we compute the lexicographically-least word of a given length on which a given TM halts?

I had this question in my exam. but my answer is wrong(I didn't receive explanations why...) $$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \...
1
vote
1answer
35 views

Why every finite language is polynomial?

I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$

1
2 3 4 5
50