Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...