All Questions

Filter by
Sorted by
Tagged with
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
1
vote
2answers
95 views

How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition $$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$ But I dont really know how to apply this information to check whether or not a grammar ...
1
vote
1answer
38 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
1
vote
1answer
23 views

I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }

I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
0
votes
2answers
60 views

Regular grammar with at most one c

I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure ...
0
votes
0answers
54 views

Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
0
votes
1answer
56 views

Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ In my opinion complement of the L language is $L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$ I choose to ...
1
vote
2answers
107 views

Is the language of words that contain a square regular or context-free? [duplicate]

$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$ I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
169 views

Prefix/suffix property of language containing only empty word

Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property? The definition says that language has prefix/suffix property requires that there is no code word in the ...
0
votes
0answers
33 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...
0
votes
0answers
26 views

How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]

I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
0
votes
1answer
36 views

Closure properties between two languages from different grammars

We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular. What if we have a regular grammar that ...
3
votes
1answer
135 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...
0
votes
1answer
59 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 ...
0
votes
0answers
129 views

Conversion from automaton to left linear grammar

I stumble across this problem: Give right linear grammar. The solution given was simple: $S\rightarrow bA$ $S\rightarrow aS$ $A\rightarrow \lambda$ $B\rightarrow bA$ $A\rightarrow aB$ Earlier ...
3
votes
1answer
795 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 ...
3
votes
1answer
218 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
17 views

Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
0
votes
0answers
135 views

When proof by induction on length string is not possible?

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ...
2
votes
0answers
80 views

How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure. Let $S$ be the start symbol ...
1
vote
1answer
114 views

Prove correctness of this (context-free) grammar

I created a context free grammar for the language which has words where twice as many a than b occur. So as example, the ...
0
votes
0answers
34 views

Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
0
votes
1answer
1k views

Construct an equivalent NFA for the given regular grammar

Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules P : A → aB, a, ε (where ε is the empty word) B → bA, b ...
0
votes
0answers
573 views

Proof of every regular language has a LL(1) grammar

I tried some examples and found that LL(1) grammar always exist. I tried searching for formal proof but didn't find any. Can someone give a formal proof for the above statement?
-1
votes
1answer
402 views

Proving that a language given by a CFG is not regular [duplicate]

Consider the language defined by the following grammar: $$ \begin{align*} &S \rightarrow E \\ &S \rightarrow \epsilon \\ &E \rightarrow E+E \\ &E \rightarrow E-E \\ &E \rightarrow \...
0
votes
1answer
156 views

Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?

Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars, i.e. a word/string that can be derived from each regular grammar. ...
0
votes
0answers
28 views

Generate a Grammar from a language(Non-CFL) [duplicate]

I tried to solve this question, We have this Language, L(g)={AA|A={0+1}*} The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side.. ...
0
votes
1answer
95 views

Questions About P, NP, languages [closed]

I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too. Given language L, which is non-recognizable, is L* context free? Is P ...
1
vote
1answer
275 views

Writing a regular grammar for a regex of decimals

So I've got the regex /[1-9][0-9]*(\.[0-9]*[1-9])?/ and I'm trying to write a regular grammar for it. I started off like this: ...
5
votes
1answer
15k views

Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
0
votes
0answers
642 views

Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa

I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows: Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB ...
3
votes
1answer
69 views

Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?

So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact. Can we use some sort of ...
3
votes
1answer
367 views

Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?

So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division. For these operations/operators, we have some properties like commutativity, ...
0
votes
1answer
120 views

How to write a regular expression to match a string that starts with the same pattern that it ends with

Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with. Let's say that we have an alphabet composed of the binary symbols: {0,1} We ...
1
vote
1answer
290 views

What is the cardinality of the set of regular grammars?

What is the cardinality of the set of regular grammars? The caveat is that I'm only interested in grammars which are 'structurally' different. Sorry I don't know how to talk about this in a formal ...
0
votes
1answer
182 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
2
votes
1answer
183 views

Can an (extended) regular grammar have multiple nonterminals in its RHS?

Standard (right) regular grammars have three kinds of rules: A <- "" A <- "a" A <- "a" B This is OK for a theoretical point of view, but a big ...
0
votes
1answer
58 views

Right linear grammar special case

According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$, does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$...
1
vote
1answer
223 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
2
votes
1answer
566 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
9
votes
5answers
1k views

Is there a known method for constructing a grammar given a finite set of finite strings?

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible ...
1
vote
1answer
361 views

Regular languages and constructing a regular grammar

I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}. How ...
1
vote
1answer
556 views

Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
2
votes
1answer
469 views

Why is my regular grammar for palindromes wrong?

I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with. I've created grammar which can generate all palindromes ...
0
votes
1answer
233 views

Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? [duplicate]

I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular. AND A DFA is a finite automata that accepts a language and also rejects ...
3
votes
1answer
3k views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
2
votes
1answer
87 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
-1
votes
1answer
40 views

Unambiguous CFG that generates regular language according to Pumping Lemma?

The pumping lemma for regular languages states: Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can ...
1
vote
1answer
799 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 ...
2
votes
1answer
63 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 rule?...