Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
51