# All Questions

25 questions
Filter by
Sorted by
Tagged with
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 ...
406 views

### Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
773 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 ...
167 views

### Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?

Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars ...
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 ...
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 ...
2k views

### DFA accepting strings with at least three occurrences of three consecutive 1's

The problem states the following: Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with ...
1k views

### How to construct regular grammar (right linear and left linear both) from regular expression?

I am interested in some kind of algorithm to achieve this. Basically here is the regular expression aa*(ab+ a)* and I want to construct a regular grammar for this....
2k views

### How did the word “production” end up being a synonym with the word “rule” in the context of Computer Science?

I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context ...
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 ...
555 views

### A context-free grammar for a language of strings with occurrence properties?

Creating a context-free grammar for the language $L_1 = \{ 0^{n} 1 ^{m} \mid m,n \in \mathbb{N} \wedge m \equiv n \mod 3\}$ is quite easy. A grammar is $$S \rightarrow \epsilon \mid 0A$$  ...
1k views

### Is it possible to build DFA for odd-length words with 1 in the middle?

$L := \{w \in \{0,1\}^* |$the length of $w$ is odd $\wedge$ 1 is in the middle of $w\}$ So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and ...
111 views

### Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
231 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 ...
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 ...
408 views

### How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

Say I have the following grammar: E -> TE' E' -> +TE'| -TE' | λ T -> (E) | id I need to build the finite state machine with the LR(0) items, But I ...
71 views

### Language of walks in a grid – context-free?

Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square ...
3k views

### Converting regular (Type-3) grammar to a deterministic finite state automaton

I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to ...
172 views

### Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite .. that's mean it may be ...
662 views

### Regular and not Regular Grammar

According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as S -> abS|a and G2 = ({S,S1,S2,},{a,b},S,P2) S -> S1ab S1 -> S1ab|S2 S2 -> a ...
88 views

### Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
3k views

### Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
20k views

### Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
I'm interested in finite state automata which have the capacity to require repetition. That is, the machine may be in a state in which the next character may be any character from set $S$, but, ...
Considering this FSM: Can someone explain me why the grammar is not: $S \rightarrow aA$ $A \rightarrow aA \mid bB \mid \varepsilon$ $B \rightarrow bB \mid \varepsilon$ Why does A not have a ...