Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
-3
votes
1answer
220 views
Is mathematics context-free?
Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions ...
1
vote
2answers
79 views
How to determine maximum stack size of LL(1) parser?
I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by ...
1
vote
1answer
45 views
Proving equivalency of regular expressions
x,y are regular expressions, prove this:
(xy+x)$^*$x = x(yx+x)$^*$*
(* in this expression is kleene star)
I am looking for a method that is applicable to prove such questions.
I know that proof ...
-1
votes
1answer
50 views
Class of given language
The language given is:
$$L = \{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \}$$
I have to find the class to which this language belongs.
Now according to my intuition, ...
1
vote
2answers
143 views
How many languages exist over the following alphabets?
(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.
For the first two alphabets in (a), we know that there ...
0
votes
1answer
46 views
Examples of non-sparse languages
All I could find is an example of sparse language.
I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the ...
1
vote
1answer
32 views
Words generated by CFG whose parse tree contain even number of $X$
Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears ...
0
votes
1answer
57 views
Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?
Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.
Is there an alternative proof that goes ...
1
vote
2answers
37 views
Language equivalent states in a deterministic parity automaton
Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are ...
2
votes
1answer
97 views
Context formal language recognizing even number of 0's and odd number of 1's
I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{...
1
vote
1answer
96 views
Looking for a formal grammar for $\{ a^{2^n} \mid n \in N\}$
The title says it all. The language $\{ a^{2^n} \mid n \in N\}$ looks quite simple. Yet I could not find a grammar that generates this language.
0
votes
1answer
80 views
Does a pushdown automata exists for the following language?
I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...
3
votes
2answers
302 views
Is DFA and Regular Expression equivalent?
The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?
If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...
1
vote
1answer
75 views
Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?
I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills.
When developing these skills one has to provide a large ...
0
votes
1answer
51 views
Question about non recursively enumerable language [duplicate]
Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?
In other words, let $R$ be the set of languages (including languages ...
3
votes
1answer
51 views
How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?
How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation ...
5
votes
1answer
98 views
Permutation of words that have matched parentheses
Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem:
Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a ...
4
votes
1answer
92 views
Is the symmetric difference of a non regular language L and a finite language f non regular?
The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$.
Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
1
vote
1answer
54 views
Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages
How can I prove this identity of languages?
My aproach is the following:
Let A, B and C to be languages, and let x to be an arbitrary string.
(A ∪ B) ⇒ x ∈ A ∨ x ∈ B
How do you proceed?
0
votes
1answer
49 views
Define a grammar to emmulate chess rules
Is it possible to define a 《chess language》:
language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?
I looked online but I cannot find a ...
1
vote
1answer
65 views
Formal grammar with variables for consistent substitutions
In a rewriting system, suppose the production rule S→xAyAz (or <S>:=x<A>y<A>z, in BNF), where S and A are ...
1
vote
1answer
35 views
Contradiction in regularity of a language
Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = ...
1
vote
1answer
60 views
Is two arrows on each state necessary in DFA? [duplicate]
In DFA, is two arrows on each state necessary?
Or it depend on language alphabets? I mean if there is $\Sigma = \{a\}$ then there should be one arrows on each state.
OR if there are $\Sigma = \{a ,...
3
votes
0answers
83 views
Generating valid sentence with respect to attribute grammar
Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To ...
2
votes
1answer
351 views
Determining if given languages are regular or recursively enumerable
I came across following problem:
Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
$L_1 =\{M|M$ accepts at most 2016 strings$\}$
$L_2=\{M|M$ accepts at least 2016 strings$\}$
...
0
votes
1answer
69 views
Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$ [closed]
How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar?
I am new to this field and I am not sure what should I do. Please help me.
0
votes
1answer
62 views
Different context-free grammars for the same language
In context-free grammar, are both the following grammars correct for the same language?
$$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$
(grammar one)
$S \to S_1 | S_2$
$S_1 \to A_1B_1$
$...
0
votes
3answers
80 views
Concatenation of language to itself zero times
I was solving this question:
Which of the following statement(s) is/are false?
$L^0=\{\epsilon\}$
$|L^0|=0$
The answer given was None. That is, none of these statements are false and ...
1
vote
1answer
41 views
“Or” in regular expressions
I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.
One basic problem I wanted to solve was ...
1
vote
1answer
350 views
Understanding facts about regular languages, finite sets and subsets of regular languages
I am aware of following two facts related to two concepts: regular languages and finite sets:
Regular languages are not closed under subset and proper subset operations.
It is decidable ...
1
vote
1answer
29 views
polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$
If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$
I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$
...
1
vote
1answer
410 views
Difference between regular language and context free language
What is nature of difference of regular language and context free language?
My guess is
RL - CFL = RL
CFL - RL = CFL
Am I correct with this?
1
vote
1answer
77 views
Both a language and its complement are not context free
Is there a language $L \subseteq \{a\}^*$ such that both $L$ and its complement are not context free?
3
votes
1answer
435 views
Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:
Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$
does not contain null string, then $R = Q + RP$ has a ...
2
votes
1answer
49 views
How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?
I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.
The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should ...
-1
votes
1answer
32 views
Regularity under set difference
Let L be a regular language.
Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$
How do I prove it is wrong?
1
vote
1answer
71 views
Context Free Grammar $L = \{a^i(b+c)^jd^k | i<j+k; i,j,k>0\}$
I'm trying to design a CFG that accept the words of the following language:
$$L = \{a^i(b+c)^jd^k \mid i<j+k; \quad i,j,k>0\}$$
My first approximation would be to do $i = j+k$ as something ...
1
vote
3answers
113 views
Infinite Union operation of Formal Languages
Is every formal language not closed under infinite union operation ?
I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any ...
0
votes
0answers
24 views
Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols
I came across the fact that
The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$
So I was wondering ...
4
votes
1answer
95 views
Identification of Formal Language
$$L = \{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\}.$$
Is $L$ DCFL or not?
According to me it should be DCFL since we can write $L$ as $\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\}$. So, now after ...
0
votes
0answers
18 views
Subclass of nonregulsr CFL's, closed under complementation? [duplicate]
Whether there exists a subclass of nonregular CFL's closed under complementation?
6
votes
2answers
130 views
Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free
This is problem 2.44 from Introduction to the theory of computation by Michael Sipser.
If $A$ and $B$ are languages, define $A \diamond B = \{xy: x \in A \land y \in B \land |x| = |y|\}$
...
0
votes
0answers
53 views
Transform grammar into LL(1) left-associative
I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this:
...
4
votes
1answer
67 views
General version of pumping lemma for regular languages, how many partitions to consider
The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$.
The article on wikipedia says, that this ...
1
vote
0answers
64 views
Proving a language is not context-free using the pumping lemma
I had a question regarding the use of the pumping lemma for a particular language I came across. I feel like I have almost solved it, but have gotten stuck on the last steps and wanted some advice. ...
0
votes
1answer
243 views
Why is this grammar an LL(2) grammar?
I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.
$$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,...
0
votes
1answer
142 views
Does adding S->SS in a context-free grammar change the language to its Kleene star?
Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky ...
2
votes
0answers
26 views
Can pushdown automata be without epsilon transitions? [duplicate]
Are pushdown automata without $\varepsilon$-transitions as powerful as those with them? Intuitively, if we need to make such a transition, we could just add the letters on the next transition we take, ...
1
vote
1answer
33 views
Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?
Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.
My proof:
Let $M = (\Sigma, Q, \delta, q_0, F)$ be an ...
1
vote
2answers
44 views
CFG where u has same number of 1s as v [closed]
$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$
Here is my attempt solution, but it is not completely correct, any hint is appreciated
...
