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