Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,511
questions
2
votes
2answers
55 views
Is the following language a Deterministic Context-Free Language?
I tried to show the following language is DCFL (Deterministic Context-Free Language):
$$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n_b(w)=n, |w|=2n\}$$
I tried to show that $L$ has a DPDA (Deterministic Push-...
1
vote
0answers
32 views
Is $L$ Deterministic Context-Free Language?
Suppose
$$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n \text{ or} |w|=n\}$$
Can we conclude that $L$ is DCFl?
I think it's DCFL because
$$L=\{a^no^n\}\cup \{\{a,b\}^no^n\}$$
Since
$$\{a^no^n\}\subseteq \{\{a,...
0
votes
1answer
75 views
Determining recursive enumerability of given languages
I came across following problem:
$L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
$L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
1
vote
3answers
60 views
A non-CFL over {a,b,c} with a non-CFL complement?
I understand uncountably many such languages exist, and the rational for it is clear to me.
I just can't think of one trivial, easy to prove example.
For instance, the complement of a^nb^nc^n is CF, ...
0
votes
0answers
41 views
How to carry out expansion in regular expression problems like ((0*10)*)?
I have been given some problems like:
Determine if each of the following strings belongs to the corresponding regular language.
i. ‘10100010’ and L((0*10)*).
iv. ‘011100101’ and L(01*10*(11*0)*)
I ...
0
votes
1answer
65 views
Which of the following languages can be represented by regular expressions?
The set of all words contained in $\{0,1\}^*$ that have an even number of 0’s and an odd number of 1’s.
I came to discover that it is possible but not sure how. Can anyone express it in a regular ...
0
votes
3answers
132 views
Difference between a regular and a non-regular language
Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then:
is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM?
is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?
4
votes
2answers
1k views
Is the language regular or not?
The language given is $L = \{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$. Is this language regular or not?
Since there is no pattern, so it should be non-regular?
Kindly help!
15
votes
1answer
557 views
Is the language of words that are unbalanced in the first half context-free?
(Practice exam question in computational models)
Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.
Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
0
votes
2answers
59 views
Declarative, interrogative, imperative, and exclamative sentences in computer languages
The following English sentences have different forms (syntax):
Declarative: You are my friend.
Interrogative: Are you my friend?
Imperative: Be my friend!
Exclamative: What a good friend you are!
...
0
votes
2answers
172 views
Same notation/terminology for union of sets and concatenation (Kleene star)?
For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
0
votes
1answer
32 views
Question about reduction Proof
I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable.
The proof used following idea:
Reduce from the $A_{TM}$ problem ...
1
vote
2answers
49 views
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ if
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ in case of:
$L_S\in RE$
$L_S\in R$
1
vote
1answer
52 views
What is the formal definition of precedence and associativity in programming language?
The concept of precedence and associativity seems straightforward.
The operator precedence is a collection of rules that reflect conventions about which procedures to perform first in order to ...
1
vote
2answers
65 views
prove/disprove regularity of languages
Let $L_1 \in REG$ and $L_2 \notin REG$ prove or disprove:
$\forall L_1 ,L_2 \text{ } $ $\text{ }L_1^C \cup L_2\in REG \lor L_2\setminus L_1\in REG$
I think that it may be disproved,
but I found it ...
1
vote
3answers
8k views
How to prove {a^(n^2) | n>0} is not context-free?
So I have a language:
$$
L = \{a^{n^2} \mid n > 0\}
$$
I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...
-1
votes
2answers
59 views
Is this grammar well-defined? How do I prove the language generated by it is regular?
I have the following problem statement:
Is G well-defined here? I am unsure of this since there's no production rule for $X, Y, Z$, and this confuses me a bit.
And secondly, how do I prove $L$ is ...
0
votes
1answer
35 views
Are these production rules for a formal grammar?
I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states ...
0
votes
1answer
47 views
Recursive languages
I need to prove if the following languages are recursive:
$A_1 \subseteq \{0, . . . , 9\}^∗ $ consists of all finite sequences of $\pi$ without the decimal point.
We may thus write $A_1 = \{3,31,314,...
0
votes
1answer
43 views
Is $B=\{a^n b^m \mid n \not= 2m\}$ a context free grammar [duplicate]
I was trying to find a grammar that generates $B=\{a^n b^m \mid n \not= 2m\}$ but I couldn't so I'm not sure that it is a CFG.
This is what I did :
$$
S\rightarrow X \mid aX \mid a \mid b \mid \...
0
votes
1answer
62 views
Is the empty string and some words of even length are elements of this set?
$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$.
I have my answers, but I need confirmation:
Is the empty string $\epsilon \in L$? Yes. Reason: ...
1
vote
1answer
156 views
Prove that the language generated by the grammar $S \to SxS \mid a$ is inherently ambiguous
With the following grammar:
$$S \to SxS \mid a$$
Is L(G) inherently ambiguous? What is the proof?
I know how to prove the grammar is ambiguous but I don't know how to prove if the grammar is ...
-1
votes
2answers
58 views
Context-free grammar for $a^{2n} b^{2n}$
I have just started learning formal languages and here is a question I am facing a little hurdle:
Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$.
This was what I got at first....
2
votes
1answer
26 views
Left recursive grammar to right recursive grammar
I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is
$$E \to E + T \mid T $$
It's equivalent right recursive grammar will be
$$\begin{align}E &\to ...
1
vote
1answer
40 views
Proof of an interesting language being non-context free
Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following:
Let $L'$ be the ...
1
vote
2answers
56 views
If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?
I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...
9
votes
2answers
314 views
What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.
So this leads to the question: ...
0
votes
2answers
44 views
Proving that a language defined by a regular expression is equivalent to a right linear grammar
After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.
Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
-2
votes
1answer
343 views
Turing machine on input w tries to move its head past the left end of the tape
Consider the language
$$ L = \{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\}. $$
Prove whether L is decidable or not.
I tried to prove ...
1
vote
1answer
57 views
Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?
The title pretty much explains the question, but still: Is the language
$$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$
context-free?
I think it isn't and would motivate that suspicion by the following ...
3
votes
2answers
395 views
If regex describes FSAs, what string formats describe Turing machines?
(Topic summary under the line.)
Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
0
votes
1answer
29 views
Poping a symbol on a PDA when Input and Stack are Irrelevant
Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special ...
1
vote
1answer
38 views
Is it true that PRIMES are in SPARSE?
I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
2
votes
1answer
159 views
Proving $\{0^{2^n}\}$ is not regular using pumping lemma
I am currently learning the pumping lemma, and encountered the following question, which I am unable to solve:
Prove that $L = \{ 0^n \mid \text{$n$ is power of 2}\}$ is not regular.
I considered $w ...
3
votes
3answers
956 views
Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular
Show that the following language $L$ is regular by describing it using a regular expression.
$$L = \{1^n w 1^n \mid n > 0 \text{ and }w ∈ \{0,1\}^*\} $$
My (apparently incorrect) answer:
Given ...
1
vote
1answer
29 views
Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$
I want to prove that the following language is decidable:
$$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$
So, I think about ...
6
votes
1answer
755 views
Are LR(k) languages and DCFLs equivalent?
In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ ...
-1
votes
1answer
86 views
Using the pumping theorem to show that this language is not context-free
Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free.
I really don't know where to start, ...
0
votes
2answers
7k views
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
i am trying to find a cfg for this cfl
L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$
is there a way to count the number of 0's or 1's in the string?
3
votes
1answer
58 views
Closure of context-sensitive languages under inverse language substitution
We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
0
votes
1answer
27 views
Proving undecidability of a language with mapping reductions
I'm referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable
I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
0
votes
1answer
49 views
Describe regular expression
I am learning about regular expression, and trying to describe a regular expression for the language L
$\qquad L = \{a^i b^j c^k \mid i+j = k\}$
What is the right approach and how to describe a ...
1
vote
0answers
31 views
Unambiguous formal grammars for a specific class of languages
Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$.
Now suppose that $q \in \mathbb{Q}$ is a positive ...
1
vote
1answer
27 views
How to define the languages of the implicit set system problems?
There are implicit versions of some set system problems or matroid problems.
A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets ...
3
votes
5answers
18k views
Regular expression for a binary string containing even number of 0's
To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it):
The regular expression for the above according to me ...
9
votes
3answers
4k views
Is Python a context-free language?
From Wikipedia: Off-side_rule#Implementation, there is a statement:
...This requires that the lexer hold state, namely the current
indentation level, and thus can detect changes in indentation ...
0
votes
0answers
38 views
Designing CFG that accepts $a^n b^m c^p$ where $n=m+p+2$
I have generated the CFG of $a^n b^m c^p$ where $m = n+p+2$:
$S \rightarrow ASC \mid \varepsilon$
$A \rightarrow aAb \mid \varepsilon$
$C \rightarrow bCc \mid \varepsilon$
I have been trying $a^n b^...
0
votes
1answer
32 views
Is a Turing Machine a Well-formed formula?
Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me.
But is it ...
-2
votes
1answer
48 views
Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.
Find the language generated by this grammar over the alphabet $\{0,1\}$:
$S\rightarrow BAB\mid CAB$
$BA \rightarrow BC$
$CA \rightarrow AAC$
...
0
votes
1answer
15 views
Show that a language with union is not regular by using pumping lemma
Given the language $L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \ \vert w\vert_a \ = \ \vert w\vert_b \} \ \cup \ \{ a,b \}^* }$
I'm really unsure how to even start because of the ...
