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 ...
2
votes
2answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
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 ...
1
vote
3answers
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 ...
0
votes
0answers
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....
13
votes
2answers
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 ...
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
2answers
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 $$ $$ ...
8
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
-2
votes
1answer
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?
0
votes
3answers
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: ...
15
votes
1answer
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 ...
2
votes
2answers
278 views

Recognizing finite state machines with repetition

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, ...
1
vote
1answer
203 views

Simple FSM question

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 ...