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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions related to formal languages, grammars, and automata theory

2
votes
0answers
13 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 ...
3
votes
1answer
41 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
35 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
44 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
44 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
27 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
2answers
43 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 ,...
1
vote
0answers
11 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
241 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
33 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
30 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
68 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
votes
0answers
17 views

What is relation between Deterministic context-free language and LL(k) languages?

Does for every DCFL P there exists some LL(1) grammar G such that L(P) = L(G)?
1
vote
1answer
38 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
44 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
23 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
26 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
46 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?
2
votes
1answer
63 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
45 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
28 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
44 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
49 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
19 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 ...
3
votes
1answer
79 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
17 views

Subclass of nonregulsr CFL's, closed under complementation? [duplicate]

Whether there exists a subclass of nonregular CFL's closed under complementation?
5
votes
2answers
72 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
18 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
36 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
46 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
20 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
92 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
28 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
38 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 ...
4
votes
1answer
57 views

How does TLC check liveness properties?

The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet ...
1
vote
1answer
41 views

Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$? [duplicate]

I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?
8
votes
5answers
2k views

Finite state automata: final states

In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram. But this seems to be a fundamentally ...
0
votes
2answers
52 views

How would a Turing Machine recognize n consecutive characters

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
-1
votes
2answers
46 views

Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
3
votes
1answer
178 views

This doesn't seem like a valid regular grammar; my instructor says it is

The following is a screenshot of a lecture slide from my programming language concepts course: According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
0
votes
0answers
13 views

Non-context free languages with word degree [duplicate]

I have stumbled across these 2 problems $L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free Given : $...
1
vote
1answer
42 views

Which word to pump in pumping lemma?

Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in ...
1
vote
1answer
36 views

DFA complexity of reverse of language recognized by “maximal” DFA

Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ ...
-2
votes
1answer
49 views

Does $R(L_1\cdot L_2)=L_2\cdot L_1$? [closed]

Does $R(L_1\cdot L_2)=L_2\cdot L_1$? Where $R$ is the reverse. I can't think about counter example
0
votes
0answers
12 views

How to convert this CFL into a CFG? [duplicate]

I'm trying to convert the following context free language into a context free grammar. $L = \{a^i b^j c^k \,|\, i+2j=4k;\, i, j, k ≥ 0\}$ I am struggling given the fact there is a large number of ...
3
votes
2answers
77 views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
0
votes
1answer
46 views

Context-free grammar from language

I'm trying to come up with a context-free grammar for the following language: $$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$ My thinking is that i can rewrite this to $$L = \{a^mb^nc^nc^m\mid 0 \le n \...
0
votes
0answers
23 views

Create a transition system where every sequence has at least twice as many $a$'s than $b$'s

Create a transition system with edges $a$ and $b$ and an initial state, such that for all possible sequences, you have that: The amount of $a$'s in the sequence is at least twice as much as the ...
1
vote
1answer
36 views

Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$

Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$ I need some tips how ...