Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

2
votes
0answers
32 views

Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in ...
0
votes
1answer
26 views

Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular [duplicate]

I'm trying to show that $L_6=\{c^n a^m b^p : n+m=p,p \geq 6\}$ is not regular. I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got ...
-1
votes
2answers
47 views

How to prove that these two languages are regular, or not regular?

I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
1
vote
1answer
36 views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
0
votes
0answers
31 views

A context free grammar for the language of even-length non-palindromes [duplicate]

I am trying to find a context free grammar for the language $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$ where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
2
votes
2answers
36 views

How can I see which language type will result from the union or intersection of different language types?

I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language. Is there a way or rule to decide this for all language types?
4
votes
1answer
86 views

Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
2
votes
1answer
79 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
-1
votes
1answer
29 views

Kleene star property: proving $(A^+)^* = A^*$ [duplicate]

I should prove that $(A^+)^* = A^*$ in a very formal way, any hints?
-5
votes
2answers
57 views

$\exists L_{1},L_{2}\subseteq\Sigma^{*}:\quad L_{1}\ne L_{2}\wedge\overline{L_{1}\cdot L_{2}}=\overline{L_{1}}\cdot\overline{L_{2}}$?

Prove or disprove $\exists L_{1},L_{2}\subseteq\Sigma^{*}:\quad L_{1}\ne L_{2}\wedge\overline{L_{1}\cdot L_{2}}=\overline{L_{1}}\cdot\overline{L_{2}} $ Where $\cdot$ means concatenation, and over ...
4
votes
2answers
677 views

Can a Language be determined by its kleene closure?

Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine? The cost of operation is measured by number of queries from ...
3
votes
1answer
97 views

Prove that regular expression is unambiguous

I've got following definition: Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true: $R = w$ and $f$ is the identity or $R = \epsilon$ and ...
0
votes
0answers
43 views

regular expression of star-height 1

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
-2
votes
1answer
51 views

How can I build a DFA for ${a^m b a^n | m+n \equiv 1 mod 3}$? [duplicate]

I have a language $\{a^m b a^n | m+n \equiv 1 mod 3\}$ $m+n$ can be 1, 4, 7, 10, 13, 16, 19, 22, ... $m+n$ is the number of all $a$'s in the word How can I build a DFA for this language?
0
votes
2answers
34 views
1
vote
1answer
55 views

How can I quickly guess if L is context-free or det. context-free?

I have a language, for example $\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$ $\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$ How can I see at a glance whether the language is deterministic ...
0
votes
0answers
81 views

How to convert the following grammar to LL(1)?

The following grammar is given: \begin{align*} M &\rightarrow d M d \\ M &\rightarrow e M e \\ M &\rightarrow f M f \\ M &\rightarrow \varepsilon \end{align*} I've checked it with ...
2
votes
1answer
16 views

Complexity of self-reducible set

I am trying to solve the following problem: A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where ...
-3
votes
0answers
58 views

Regular expression question

I have the following question in my homework but I'm not sure what the answer is. I'd appreciate it if someone could help me. The question is as follows: The language of regular expression ...
-2
votes
1answer
68 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ ...
0
votes
0answers
16 views

Pumping Lemma for CFG - How to do it? [duplicate]

I'm literally so confused on how to even start this problem of proving that the given language is not Context Free. L = {a^i b^j c^k d^l | i = k and j = l} I ...
1
vote
2answers
59 views

Are regular languages closed against an intersection that keeps words with the same number of ones?

How can we show that the class of regular languages is closed under the following operation? Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$. The operation is: $$\{x \in L_1 \mid \text{ for ...
2
votes
1answer
57 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...
0
votes
0answers
45 views

Why is this language is not context-free? [duplicate]

Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
0
votes
2answers
73 views

Intersection of a language with a regular language imply context free

Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is ...
0
votes
2answers
72 views

Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free? $$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= ...
1
vote
1answer
56 views

Is this language regular or non-regular: {ww : w ∈ {a,b}* } [duplicate]

This is a question from a text book that's giving me some trouble. The question is: Determine whether or not this language is regular. Justify your answer. $$L = \{ww : w \in \{a,b\}^* \}$$ I ...
-1
votes
1answer
42 views

NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$

I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$. Is there a two-state NPDA ...
0
votes
1answer
33 views

True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

Question: Is the following statement true or false? If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable I thought that since every language is automatically of type 0, it follows that $A ...
4
votes
1answer
58 views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
0
votes
1answer
34 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
0
votes
1answer
38 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
3
votes
1answer
141 views

How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are: $|y|\geq1$ $|xy|\leq p$ $\forall i \geq 0:xyiz\in L$ I don't understand why the length of ...
2
votes
0answers
34 views

Removing hidden ambiguity in grammar using left factoring

I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new ...
1
vote
1answer
33 views

Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is: Find a regular grammar that generates each of the following languages: ...
0
votes
1answer
69 views

If L1 ∪ L2 and L1 are regular, is L2 also regular?

This is a problem in a theory of computation book that's stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I ...
0
votes
0answers
24 views

How these languages are context free and regular [duplicate]

I found these statements in my textbook without proof. If L is a Context Free Language over a one symbol alphabet then L is regular. Is there no context free language on one symbol ...
0
votes
1answer
46 views

Pumping Lemma confusion

I have the following language... $$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$ Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is ...
2
votes
1answer
64 views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
2
votes
1answer
129 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...
1
vote
1answer
34 views

Closure properties between 2 languages of different types [duplicate]

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
1
vote
1answer
84 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
2
votes
0answers
25 views

Tightest upper bound on length of distinguishing string in Hopcroft's algorithm

Hopcroft's algorithm is an algorithm for DFA minimization that produces a table identifying which pairs of states are distinguishable. What is the tightest possible upper bound (with proof) on the ...
0
votes
0answers
25 views

What is the procedure for converting this finite automaton into a regular expression? [duplicate]

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
0
votes
0answers
17 views

non-regular context free language with logarithmic stack usage [duplicate]

Can you suggest a context-free language $L$, which is: non-regular has a PDA which accepts all $w\in L$ and uses maximum stack space of $\log(|w|)$.
0
votes
1answer
96 views

What is meant by the notation $L(…)$?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...
0
votes
1answer
65 views

How do I show that a^n w b^n is not regular?

$\ \sum= \{a,b\} $ Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the ...
0
votes
1answer
60 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
0
votes
1answer
55 views

Union of finite and non-regular language [duplicate]

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular: Prove/Disprove: $C\cup B$ isn't regular. Thoughts: My intuition says this is true, but I need an idea to prove it. Since I ...
0
votes
1answer
55 views

Three languages and how to decide if they are regular [closed]

From following languages which one is regular and why others are not?And what is the regular expression for regular one. $L_1= \{wxwy | x,y,w \in (a+b)^+\}$ $L_2 = \{xwyw | x,y,w \in (a+b)^+\}$ ...