Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
3
votes
1answer
60 views

Can you diagonalize a language out of CSL?

In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
-1
votes
0answers
35 views

A formal proof of Arden's Theorem [duplicate]

I have been searching internet for a correct proof of Arden's Theorem and have searched some book also. Many proofs seem to be completely wrong, filled with fallacies and can't trust what is written ...
1
vote
1answer
27 views

Test whether words of less a's than b's or c's but not at the same time is context-free

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so. The closest ...
1
vote
1answer
68 views

Are programs just "words" of a formal language?

Every formal language is a subset of E*. Let's say this formal language is python. If a program is syntactically correct, then the Python Automata accepts the "word", which is the program. ...
1
vote
1answer
26 views

Given two languages $A,B \subseteq \Sigma^*$, prove that $A/B$ is semi-decidable if both the languages are semi-decidable

I have found two interesting questions regarding the quotient of languages, described as: $A/B=\{w \mid \exists z\in B\land wz\in A\}$ The first one is: Let $A$ and $B$ be regular languages, prove ...
2
votes
1answer
89 views

Dragon book 4.4.5 exercise?

...
1
vote
1answer
30 views

Find a transducer that maps a given deterministic process to another

Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
0
votes
1answer
40 views

Language for starting and ending with same symbol

Alphabet = {a,b} should null string be the part of this language? L ={^,a,b,aa,bb,abba ......} I have seen on different sources not including null string. Is null string a part of this language or not?...
3
votes
1answer
67 views

Context free grammar for strings with more $a$'s than $b$'s

I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$...
0
votes
2answers
54 views

How to define a formal language for describing procedural activities

I do not have a formal computer science background here so I am looking for pointers. How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing ...
0
votes
0answers
49 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,...
1
vote
2answers
209 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
3answers
64 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
1answer
67 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
0answers
46 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 ...
4
votes
2answers
2k views

Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ 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!
0
votes
2answers
76 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! ...
1
vote
2answers
52 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
54 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
67 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
votes
2answers
61 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
49 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
44 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 \...
1
vote
1answer
159 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 ...
2
votes
1answer
30 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
57 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
322 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: ...
3
votes
2answers
397 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 ...
1
vote
1answer
58 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 ...
0
votes
1answer
31 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
40 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
3answers
73 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....
0
votes
1answer
33 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
1answer
30 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 ...
3
votes
1answer
62 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) ...
1
vote
0answers
32 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
29 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 ...
0
votes
1answer
50 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 ...
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
35 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 ...
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
vote
2answers
114 views

How is CLR(1) grammar more powerful than LALR(1) grammar

I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
0
votes
0answers
27 views

Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]

Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma. So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...
-2
votes
1answer
49 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$ ...
1
vote
1answer
48 views

Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less. I thought about proving this in two ways: ...
-2
votes
1answer
49 views

CFG for $\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $

$L=\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $ Any help would be appreciated.
1
vote
1answer
37 views

PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

On my compilation theory exam we had the following problem: Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
14
votes
4answers
7k views

Are modern programming languages context-free?

Which language class are today's modern programming languages like Java, JavaScript, and Python in? It appears (?) they are not context-free and not regular languages. Are these programming languages ...
1
vote
0answers
45 views

Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...

1
2 3 4 5
51