Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,455
questions
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$
