Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

4
votes
2answers
141 views

Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
1
vote
0answers
31 views

What are resources that I can use to learn about formal langauges?

What are some good resources for practice problems on formal languages? Every textbook I've seen contains few practice problems with even fewer answers. I would like a resource that has questions with ...
-1
votes
1answer
44 views

“Best” automaton for a regular language

For a given regular language, there are multiple finite automata. How do we determine which one is best?
1
vote
1answer
56 views

Show that the following construction is not a correct proof for Context Free Grammars

Give a counterexample to show that the following constructions are not correct proofs for the star operation: Given a CFG $G = (V,Σ,R,S)$, add the new rule i) $ S → SS$ or ii) $S → SS|ε$. ...
0
votes
3answers
85 views

Why is $\{1^n \mid n > 1\}$ regular?

Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$ regular? The $n$ is unbounded. I know a DFA can be drawn, which means the ...
1
vote
1answer
47 views

Regular languages closed under quotients with arbitrary languages

When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final ...
0
votes
1answer
33 views

Why is this language not context free?

I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not ...
0
votes
3answers
36 views

Difference in having * inside vs outside of brackets for NFA

If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for ...
0
votes
1answer
38 views

How to check if my language is context-free can't seem to solve it using pumping lemma

I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to ...
1
vote
1answer
28 views

Definition of complexity classes?

My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$): $$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an ...
1
vote
1answer
54 views

Proving specific prefixes of regular languages are regular

There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets: $$ \{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \}$$ $$ ...
0
votes
3answers
51 views

Why does it seem as if I can apply the Pumping lemma to a language that is regular?

We learn about the Pumping Lemma at the class and I tried to make few examples to understand it... There I make this example: Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all ...
2
votes
1answer
65 views

Find a regular language that is “infinitely between” two other regular languages

Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq ...
8
votes
4answers
138 views

If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular to? I try to find a way to prove it... I can't assume of course that $L_1,L_2$ ...
-1
votes
1answer
52 views

How to write Context-free Grammar for this language? [closed]

I am trying to teach myself how to write Context-free Grammar for different languages. I have an example language I am trying to work out and this is the answer I came up with, does it make sense? ...
2
votes
1answer
56 views

Meaning of $\stackrel{*}{\rightarrow}$ production rule?

I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages. What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?
1
vote
1answer
55 views

If c ∈ Σ denotes terminals, then is Y = Σ∖{c} the set of non-terminals?

If $c\in \Sigma$ denotes terminals, then is $Y=\Sigma \setminus \{c\}$ the set of non-terminals? These notations are used here, p. 379. But I cannot find their definitions. So what I'm asking is, is ...
2
votes
2answers
47 views

$A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition: Let $\Sigma = \{0,1\}$. If $A$ and $B$ are ...
0
votes
1answer
103 views

Languages that are not subset, but are union

Are there examples of regular languages $L_1$ and $L_2$, where $L_1$ and $L_2$ is not a subset of each other but that $(L_1 \cup L_2)^* = L_1^* \cup L_2^*$ ?
1
vote
1answer
51 views

How to prove a L=L(G) without knowing the L? [closed]

How does one prove L(G)=L if the language is not given and only the grammar G is given? If there is no pattern to be seen in the grammar that would create the strings w of a language L, how would you ...
0
votes
0answers
58 views

Describe the language generated by a given context free grammar

I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. $$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA ...
1
vote
1answer
84 views

If two languages together cover all words and one is regular, is the other one as well?

If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ necessarily regular? I think that the answer is yes, but I'm not sure ...
7
votes
1answer
286 views

Class of the language only containing the empty string?

$L = \left \{ \epsilon \right \}$ Clearly this language is finite so this must be a regular language. Now since every regular language is Context Sensitive, $L$ is a CSL. We can define the grammar ...
0
votes
2answers
55 views

Can a deterministic language be accepted by a deterministic Push Down Automaton?

I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic ...
-2
votes
2answers
35 views

Alternative for regular expression

Could the following be considered as an alternate regular expression for regex $a(aa)^*$? $a^k$ where $k$ is odd. Could the following be considered as an alternate regular expression for regex ...
0
votes
1answer
94 views

How do I prove that a language is deletion closed?

For example, how could I prove that the following language is deletion closed: {$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0} The reason seems obvious to me, I just can't see a way to prove it.
2
votes
1answer
66 views

How to remember NFA's choice on a certain computation?

I'm working on solving the question answered at this page but with different values at the table, my alphabet is {a,b,c} Words that have the same right- and left-associative product Currently I'm in ...
1
vote
1answer
98 views

Proving grammar only generate strings that is multiple of 3

Hello I have an exercise for homework and I was hopping to get some hints in order to solve it. num-> 11 | 10 num' 01 | num 0 | num num num'-> 00 num' | 1 num' | ε I need to prove that my ...
0
votes
0answers
19 views

NFA to DFA, where DFA got exactly $2^n$ states used [duplicate]

I have been trying to create NFA with $n \ge 3$ states, where DFA got exactly $2^n$ states reached. i.e. none of the states in DFA will be unused thus disappear. So far I have not been able to ...
1
vote
1answer
197 views

Why is the complement of a language that is not regular also not regular?

In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not ...
7
votes
1answer
116 views

Context-free languages not closed under making them “extension-free”

For a language $L$, define: $$ NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\} $$ I'm trying to show context-free languages are not closed under this operation. I've been ...
-1
votes
2answers
98 views

Is the complement of { www | … } context-free?

Is $\left ( 0+1 \right )^{\ast }-\left \{ www : w \in \left \{ 0,1 \right \}^{\ast } \right \}$ context-free? If it is what is a grammar generating it?
1
vote
3answers
151 views

Why is the set of all regular expressions classified as context-free, instead of regular?

As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?
3
votes
1answer
116 views

Is {ww^r ww^r} a context-free language?

Is the language $L = \{w w^r w w^r \mid w \in \Sigma^*\}$ context-free? ($w^r$ is the reversal of $w$.) I heard that by using the pumping lemma, we can only prove that a language is not context-free, ...
3
votes
2answers
223 views

Partitioning any language to regular?

One time I saw a theorem that says something like any language can be partitioned into regular languages, but I can't remember exactly what the theorem is. Could somebody tell me, is this true? What ...
2
votes
1answer
37 views

Significance of including $S \to ε$ production rule in regular grammar?

Why a production rule $S\to ε$ has been included in the definition of regular grammar? In that case, why it is restricted for $S$ (start symbol) to be present on right hand side of any production ...
-2
votes
2answers
94 views

Union and intersection of a regular and a non-regular language

Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages? We know that two ...
1
vote
2answers
80 views

If L is regular show that even (L) is also regular

I am stuck on the following question If L is regular show that even(L) is also regular where even(L) = {even(w) : w ∈ L} w is a string in L even(w) is the string obtained by extracting from w the ...
0
votes
1answer
55 views

What language should this NFA recognise?

I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise From my understanding, this NFA accepts strings that ...
2
votes
1answer
44 views

If a language has any single occurrence of a letter, is it not context-free?

From what I understand, the rules for CFL from my notes say: If $L$ is a language and • for all integers $N$, • there is a string $w \in L$ of length greater than $N$ such that • for all ways of ...
-1
votes
2answers
29 views

Context-free Grammar To Generate $L=\{a^nb^k | 1 =< n =< 2k } [duplicate]

I need to write a context-free grammar for this Language : $\L = {a^nb^k | 1 =< n <= 2k} Please help me solve this problem! Thanks.
0
votes
1answer
43 views

Example Context free grammar

Is there a nice way to give context free grammar for $$\{a^nb^ma^kb^l:n+m=k+l\}?$$ From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack ...
0
votes
1answer
50 views

Union of right congruence relations

Since we started talking about relations on languages and so on i keep on struggling with this subject. So now iam faced with two questions where i really dont know how to start. First of all, ...
1
vote
2answers
95 views

Formal construction of PDA intersecting a DFA

Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$ and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$ What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$ I don't ...
-1
votes
1answer
60 views

Infinite Union of non-regular languages

Is infinite union of non-regular languages $L_i$ that form a chain such that $L_i\subseteq L_{i+1}$ always non-regular? Or is there a possibility that it be ever regular? Is there an easy way to ...
-1
votes
1answer
55 views

How to prove the linear context free languages are closed under gsm mapping?

I'm stuck on the following question: How to prove the linear context free languages are closed under gsm mapping?
0
votes
1answer
49 views

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? [duplicate]

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.
-2
votes
2answers
37 views

Why is the intersection of CFL and RL not always RL?

Suppose M is a CFL and N is aa RL. Then wouldn't the language generated by the intersection of M and N contain strings, some of which are accepted by both DFA and PDA? So if they are accepted by a DFA ...
1
vote
2answers
104 views

Unrestricted grammar for the language of strings whose length is not $2^n$

The following exercise is inspired by an old exam question (note that this is not the question): Let us define a single-letter alphabet $\Sigma = \{a\}$ and the language $L = \{ w \in \Sigma^*: |w| = ...
3
votes
1answer
63 views

Proving that picking odd-numbered symbols can create the universal set from a non-regular language

Let's define the following operations: $odd(string) = $ odd characters of $string$, $even(string) = $ even characters of $string$ Now say we have some language $L$, we will then define the ...